(17298) 오큰수

https://www.acmicpc.net/problem/17298

단계별로 풀어보기

38단계(스택, 큐, 덱 2) 2번째

 

 

 

스택으로 풀 수 있는 유명한 문제 중 하나인 오큰수. 스택 안에 수(인덱스)를 하나씩 넣으면서 자기보다 큰 수를 만나면 하나씩 꺼내며 갱신한다. 스택 안에 남아있는 수의 의미는 아직 오큰수를 찾지 못한 수들이므로, 탐색이 끝난 뒤 남아있는 수들의 오큰수는 -1이다.

스택이 비어있을 때는 꺼내지 않도록 예외 처리를 할 수도 있으나, INF값을 가진 가상의 0번 인덱스를 넣어도 구현 가능하다.

 

참고로 이 과정에서 스택에는 항상 이미 존재하는 스택의 top의 수보다 작은 수가 들어가므로 스택 내부는 항상 내림차순으로 정렬되어있다. 이렇게 정렬된 스택을 모노톤 스택이라고 하는데, 모노톤 스택 그 자체로는 큰 의미가 없고 만드는 과정에서 발생하는 정보로 이런 문제를 풀 수 있다.

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(n+1);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  stack<int> s;
  s.push(0);
  v[0]= 1000001;
  
  for(int i=1;i<=n;i++){
    while(v[s.top()]<v[i]){
      v[s.top()]= v[i];
      s.pop();
    }
    
    s.push(i);
  }
  
  while(!s.empty()){
    v[s.top()]= -1;
    s.pop();
  }
  
  for(int i=1;i<=n;i++)  cout << v[i] << " ";
  
  return 0;
}