[알고리즘] 백준 17298 오큰수 // 스택으로 탐색대상 줄이기

* 완탐풀이

• 정방향으로 탐색하면서 나보다 큰 수를 찾는다.
• 시간복잡도 : N(N-1)/2 -> 불가능

• 역병향으로 탐색하면?
• 5 입장에서 좌측을 탐색한다.
• 3의 오큰수는 나(5)다.
• 2입장에서 나를 오큰수로 가질만한게 있나? -> 없음 -> pass
• 이때, 3의 오큰수는 이미 정해져있다. -> 탐색할 필요가 없었다!
• 1입장에서도 나를 오큰수로 가질것이 없다
• 8입장에서는 3을 볼필요가 없다.(이미 오큰수가 있음)
• 오큰수가 없는것중 나(8)를 오큰수로 가질수있음 --> 내가 오큰수다.
• 10입장에서 8의 오큰수는 나다.
• len만큼 다돌았는데 오큰수가 없으면, 오큰수가 없는것이다.
• 하지만, 시간복잡도는 정방향과 비슷하다.
• 시간복잡도가 많은원인 : 이미 오큰수가 있는 숫자(3 같은)를 탐색하는 비용이 크다.
• 개선 : stack에 넣고, 오큰수가 정해진것들은 pop 해버리면 탐색범위를 줄일수 있다!

 

* 스택풀이

• 볼 필요가 없는 숫자를 미리 pop 한다면, 시간복잡도를 줄일수있을것이다!
• i) 좌측을 보면서, 나보다 작은숫자는 나를 오큰수로한다. -> 나를 오큰수로 기록하고 pop! -> 탐색할필요 없음
• ii) 나보다 크거나 같은 숫자가 좌측에 있는경우 -> 그 숫자의 오큰수는 뭐가 될지모름 -> 추가 탐색필요
• i, ii의 경우모두 나는 push 해야함.
• 이미 오큰수가 있는 숫자는 제외해야 한다. -> 위 조건을 지킨다면 자동으로 구현된다.(pop 되었을것 이므로)
• 다 돌았는데 남은 숫자는 오큰수가 없는 수이다. -> ans[idx] = -1 기록

 

* 전체코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n;
vector<ll> arr;
ll ans[1000000 + 4];
stack<pair<ll, ll>> s; // idx, val

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

    cin >> n ;

    for (int i = 0; i < n; ++i) {
        ll tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }
    
    s.push({ 0,arr[0] });

    for (int i = 1; i < n; ++i) {
        ll cur = arr[i];
        while (s.size() && s.top().second < cur) {
            ans[s.top().first] = cur;
            s.pop();
        }
        s.push({ i,cur });
    }

    while (s.size()) {
        ll idx = s.top().first;
        ans[idx] = -1;
        s.pop();
    }

    for (int i = 0; i < n; ++i) {
        cout << ans[i] << " ";
    }
    
    return 0;
}