[백준 - 17298] 오큰수 - C++

분류: 스택 /

 

문제

문제 링크

문제 설명

크기가 N인 수열 A = A₁, A₂, ..., A_N이 있다. 수열의 각 원소 A_i에 대해서 오큰수 NGE(i)를 구하려고 한다. A_i의 오큰수는 오른쪽에 있으면서 A_i보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A₁, A₂, ..., A_N (1 ≤ A_i ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

풀이

- Monotonic Decreasing Stack

#include <iostream>
#include <stack>
using namespace std;

struct e { int idx, val; };

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);

  int n; cin >> n;
  int ans[n];
  stack<e> S;
  for(int i=0; i<n; i++){
    int x; cin >> x;
    while(!S.empty() && S.top().val < x){
      ans[S.top().idx] = x;
      S.pop();
    }
    S.push({i, x});
  }
  while(!S.empty()){
    ans[S.top().idx] = -1;
    S.pop();
  }

  for(int x:ans)
    cout << x << ' ';
}

monotonic decreasing stack에서 자신을 pop 시킨 요소가 NGE다.

따라서 스택을 만들고 `pop`마다 `ans`의 pop되는 요소의 인덱스의치에 `x`를 저장한다.

ans[k] = x는 NGE(k) = x를 의미하고 이는 "k번째 입력을 x가 pop시켰다."로 해석될 수 있다.