(C++) - 백준(BOJ) 17298번 : 오큰수 답

www.acmicpc.net/problem/17298

17298번: 오큰수

stack으로 푼 문제였습니다.

 

풀이방법

 1. 인덱스를 넣어줄 스택을 만들어줍니다. 입력을 받은 뒤, 스택이 비어있지 않다면 현재 값보다 작은 동안 해당 인덱스의 값을 갱신해주고 스택 pop해줍니다.

 

 2. 그렇게 모두 수행한다면 찌꺼기가 남는데 오른쪽에 더이상큰 값이 없는 경우에 해당합니다. 그런 값들의 index를 저장하고 있는 stack에 대해 stack이 빌 때까지 top에 해당하는 인덱스의 값들을 -1하고 pop해줍니다.

 

 3. 정답을 출력해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1000001],ans[1000001];
stack <int> s;
int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++){
        while(!s.empty() && a[s.top()] < a[i]){
            ans[s.top()] = a[i];
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty()){
        ans[s.top()] = -1;
        s.pop();
    }
    for(int i = 0; i < n; i++) cout << ans[i] << ' ';
}