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

www.acmicpc.net/problem/17298

17298번: 오큰수

 

 

 

알고리즘 종류

자료구조

스택

 

 

 

사고 과정

왜 스택으로 풀 수 있을까요? 문제에서 제시된 오큰수의 정의를 보면, Ai의 오른쪽에서 Ai보다 큰 수들 중에 가장 왼쪽에 있는 수 라고 합니다. A2의 오큰수는 A6의 7이 됩니다. 그런데 A2만 7이 오큰수이지는 않습니다. A3, A4, A5도 7이 오큰수 입니다.

이는 마치, 스택에 3,5,2,3,4가 있는 상태에서 7보다 작은 수는 모두 꺼내서 오큰수를 7이라고 명명하는 것과 같아 보입니다. 그래서 스택으로 풀었습니다.

 

 

 

구현(C++)

#include <iostream>
#include <stack>
 
using namespace std;
 
int n;
 
int arr[1000001];
stack<pair<int, int> > s;
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> n;
    
    int x;
    for(int i=0; i<n; i++){
        cin >> x;
        
        if(s.empty()) s.push({x, i});
        else {
            while(!s.empty()){
                if(s.top().first >= x) break;
                arr[s.top().second] = x;
                s.pop();
            }
            s.push({x, i});
        }
    }
    
    while(!s.empty()){
        arr[s.top().second] = -1;
        s.pop();
    }
    
    for(int i=0; i<n; i++) cout << arr[i] << " ";
    
}

 

 

 

시행착오