[BOJ] 오큰수 - Compy's Blog

오큰수

TimeLimit	MemoryLimit	Condition	TAG
1s	512MB	(1 ≤ N ≤ 1,000,000 1 ≤ Ai ≤ 1,000,000)	Stack

전형적인 모노톤 스택 연습 문제입니다.

모노톤 스택?
모노톤 스택(Monotonic Stack)이란?#
모노톤(Monotonic)이라는 말은 “단조로운”, “한 방향으로 증가/감소하는” 이라는 뜻을 가지고 있습니다. 그래서 이걸 스택에 적용해보면 어떻게 이해할 수 있을까요?
바로 스택 내의 모든 요소들이 일정한 순서(오름차순 또는 내림차순)을 유지하는 형태의 스택을 말한답니다
간단한 작동 원리#
제가 핵심 원리로 생각하는 것은 새로운 요소를 추가할 때마다 이 스택의 단조성을 유지하는 것입니다.

모노톤 스택은 당연히 시간 복잡도가 O(N)으로 단순히 본 문제를 풀면 시간 초과가 나는 코드를 효과적을 줄일 때도 쓰이는 등 정말 여러 문제에서 쓰입니다. 뭐 빌딩이 보인다. 내 친구가 보인다 등등 뭐 이런 문제에서 많이 쓰이더라구요!

그래서 이런 모노톤 스택 연습해보시길 강추 드립니다.

정답 코드

#include <iostream>
#include <stack>

using namespace std;

void print(int* res, int n){
    cout << "\n";
    for(int i = 0; i < n; i++){
        cout << res[i] << " ";
    }
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s;
    int n;
    cin >> n;
    
    stack<int> stack;
    int result[1000000];
    int origin[1000000];

    for(int i = n - 1; i > -1; i--){
        result[i] = -1;
        origin[i] = -1;
        cin >> origin[i];
        while(!stack.empty() && origin[i] > origin[stack.top()]){
            result[stack.top()] = origin[i];
            stack.pop();
        }
        //print(result, n);
        //cout << origin[i] << " " << (stack.empty() ? 0 : stack.top()) << "\n\n";
        stack.push(i);
    }
    
    for(int i = n-1; i > -1; i--){
        cout << result[i] << " ";
    }
    
    
}