[백준 17298번] 오큰수 (C++)

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

 

O(N^2)으로 풀면 쉽게 풀리지만 그러면 골드난이도가 아닐 것이다. N이 크기 때문에 O(N) 혹은 O(N Log N)으로 풀어내야한다.

어떻게 최적화 할 수 있을까?

 

2, 9, 10, 2, 11 예제를

막대로 그려보면 다음과 같다.

 

그리고 각 A, B, C, D, E의 꼭대기에서 오른쪽으로 갈 때 가장먼저 부딫히는 막대의 크기를 출력해야하는 문제다.

 

아하.. 그렇다면 맨 오른쪽에서부터 막대를 새우면서 진행하면 될 것 같다. 

1. 11 막대를 새운다.

2. 2막대를 새우고 11과 비교한다. 오큰수: 11

3. 10 막대를 새우고 2와 먼저 비교한다. 앗.. 2보다 10이 더 크다. 즉, 이제 2는 절대로 누군가의 오큰수가 될 가능성이 없다. 그러므로 2는 이제 비교하지 않겠다. 11과 비교하자. 11이 더 크다. 오큰수: 10

4. 9막대를 새운다. 새워져있는 벽들 중 가장 작은 것과 비교한다. 10이다. 오큰수: 10

5. 2막대를 새운다. 9와 비교한다. 오큰수 : 9

 

여기서 가장 작은 것을 비교하는데 10 8 이런식으로 새워져있을수도 있지않은가? 라고 반문할 수 있다. 그러나 현재 막대가 새워져 있다는 것은 오름차를 필연적으로 만족하게된다.

 

아하... 그렇다면 스택을 사용하면 되겠다.

 

그 중에서도 스택을 내림차로 유지하는 모노토닉스택 방식으로 진행하자. 

 

                                                                         2

                                                         9             9

                      2             10               10            10

  11                11             11               11             11

stack.   ->  stack -> stack.  ->. stack  -> stack 

 

여기서 top은 가장 작은 수, 즉 새워져있는 가장 왼쪽의 값이 된다. 그러므로 오큰수를 만족하며, 만약 지금 비교막대가 더 크면 top은 가치가 없으므로 pop하고 다음것과 비교한다. 그리고 모든 값이 필요없게 되면 -1을 출력하면 된다.

 

난 모노톤스택을 저번에 풀어보고 넘어갔다가 이번에 공부했다. 저번에도 모노톤스택 문제를 pq로 풀었는데 이번에도 같은 행동을 했다..;

 

결국 어차피 pq로 최소값을 가져오지 않아도 top이 최소값인 것을,,, 쓸모없는 연산을 추가했었다.

 

그래서 정답코드 보면 스택의 변수명이 pq이다. 여기서 priority_queue로 바꿔도 정답이 된다. 그러나 로그시간으로 폴리노미얼타임보다 느리다.

 

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N; cin >> N;

    vector<int> arr;
    vector<int> ans;

    for(int i = 0; i < N; i++){
        int tmp; cin >> tmp;
        arr.push_back(tmp);
    }

    stack<int> pq;

    for(int i = N - 1; i > -1; i--){
        int value = arr[i];

        while(!pq.empty()){
            int next = -pq.top();
            
            if(value < next) {
                ans.push_back(next);
                pq.push(-value);
                break;
            }else{
                pq.pop();
            }
        }
        

        if(pq.empty()){
            ans.push_back(-1);

            pq.push(-value);
        }
    }

    for(int i = N - 1; i > -1; i--) cout << ans[i] << ' ';
}