BOJ 17298 오큰수

BOJ 17298 오큰수

문제

처음 딱 본 순간 생각보다 간단한데? 하면서 그냥 아래와 같이 naive 하게 풀었다.
이때는 빨리 풀고 다음문제 해야지라는 생각에 입력 크기를 못본듯.

최초 시도

// 2021.09.11 11:10:03
// 17298 http://boj.kr/17298
#include <bits/stdc++.h>
using namespace std;

int nge(vector<int> &a, int i){
    int ret=-1;
    for (int j = i+1; j < a.size(); j++)
    {
        if(a[j] > a[i]){
            ret = a[j];
            break;
        }
    }
    return ret;
    
}

int main(){
    int n;
    cin >> n;
    vector<int> a;
    for(int i=0;i<n;i++){
        int ai;
        cin >> ai;
        a.push_back(ai);
    }

    for(int i=0;i<n;i++){
        cout << nge(a,i);
        if(i<n-1) cout << " "; 
    }

}

이렇게 풀고 나니 시간초과가 떴다.
그제서야 입력 크기를 보니 너무 당연했다.
(1e6)^2 이라니.. 너무 불가능했다.

그리고는 입력과 동시에 오큰수가 정해지는 케이스가 있음을 깨닫고 그걸 이용해 시간을 줄여봤다.

개선 시도

// 2021.09.11 11:10:03
// 17298 http://boj.kr/17298
#include <bits/stdc++.h>
using namespace std;

class Num
{
public:
    Num(int n, int i)
    {
        num = n;
        idx = i;
    }
    int num;
    int idx;
};

int main()
{
    int n;
    cin >> n;
    stack<Num> s;
    vector<int> a;
    vector<int> result(n, -1);
    for (int i = 0; i < n; i++)
    {
        int ai;
        cin >> ai;

        //바로 처리할수 있는건 바로 처리
        a.push_back(ai);
        if (s.size())
        {
            Num &top = s.top();
            if (top.num < ai)
            {
                s.pop();
                result[top.idx] = ai;
            }
        }
        s.push(Num(ai, i));
    }

    //남은것들
    while (s.size())
    {
        Num &ai = s.top();

        if (ai.idx != (a.size() - 1))
        {
            for (int j = ai.idx + 1; j < a.size(); j++)
            {
                if (a[j] > ai.num)
                {
                    result[ai.idx] = a[j];
                    break;
                }
            }
        }

        s.pop();
    }

    for (int i = 0; i < n; i++)
    {
        cout << result[i];
        if(i!=n-1)
        cout << " ";
    }
}

결과는 또 시간초과. 시간이 줄어들긴 했겠으나 Worst Case에서는 미미한 수준이다.
이때는 바로 정해지는 경우를 고려하긴 했지만 나머지를 기존과 같은 방식으로 하나하나 순회하며 처리했다.
그리고 든 생각이

스택에 [3] 이 들어있으면
5가 들어오면 3의 오큰수가 바로 정해지니
더 이상 건들 필요가 없어 스택에서 빼버리고.
다시 [5]만 들어있는 상황이 되었을 때, 2가 들어오면 오큰수가 정해지지 않아서
[5,2]가 된다.
다음으로 7이 들어오면 2의 오큰수는 바로 정해지고 스택은 [5]가 되며
5의 오큰수도 7로 할 수 있어 스택은 최종적으로 비게 된다.

그런데 멍청하게도 이렇게 [5,2] 에서 2가 결정된 후 빠졌는데 5에대해 다시 비교하는 것을 어떻게 구현할지 한참 고민하고 시도하고를 반복했다.
그래서 개선 코드를 짜면서 남는걸 처리할 방법이 떠오르지 않아 그냥 돌렸을 때
결과가 [5, -1, 7, -1] 이렇게 나왔다.

지금 생각해보니 딱 그만큼 부족했었다고 생각이 든다. 여기서 잘못 나아가서 기존 방법을 재 도입.. (시간이 줄어들긴 하니) 했다.

결국 if()를 while()로 바꾸면서 풀긴 풀었으나 뭔가 찝찝하여 며칠 혹은 몇 주 후에 다시 풀어보려고 한다.

최종 코드

// 2021.09.11 11:10:03
// 17298 http://boj.kr/17298
#include <bits/stdc++.h>
using namespace std;

class Num
{
public:
    Num(int n, int i)
    {
        num = n;
        idx = i;
    }
    int num;
    int idx;
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    stack<Num> s;
    vector<int> result(n, -1);
    for (int i = 0; i < n; i++)
    {
        int input;
        cin >> input;

        while(s.size() && input > s.top().num){
            result[s.top().idx]= input;
            s.pop();
        }

        s.push(Num(input,i));
    }

    for (int i = 0; i < n; i++)
    {
        cout << result[i];
        if (i != n - 1)
            cout << " ";
    }
}

결과