오큰수

추천 문제를 받아서 풀어봤다. 생각보다 금방 풀었지만 내가 문제 유형을 Stack 으로 봐서 가능했던거 같다. 만약에 Stack 풀이 인줄 몰랐으면 좀 뻘짓을 많이 헀을거 같다.

이 문제는 지금 숫자를 기준으로 오른쪽에 위치한 숫자가 자신보다 더 크고 가장 왼쪽에 있는 숫자를 원한다. (문제 내용이 좀 어지럽다)

Stack 풀이를 활용 했으며, 전에 나보다 작은 숫자가 Stack 에 쌓여 있으면 계속 pop 해줘서 Time Complexity 를 지킬 수 있었다.

확실히 예전에 영상을 봐서 그런가.. TLE 에 대한 생각이 조금 늘어난거같다.

10^6 승 풀이는 완전 탐색으로 절대 풀 수 없는 문제라는 걸 아니깐 좀 더 깊게 생각하게 되는거같다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N; 
int nums[1000001];
int answer[1000001];  

void Input(){
    cin >> N; 
    for(int i = 0; i < N; i++){
        int next; 
        cin >> next; 
        nums[i] = next; 
    }
}


void Solution(){
    stack<pair<int,int>> numsStack; 
    memset(answer,-1,sizeof(answer)); 
    for(int i = 0; i < N; i++){
        int currNum = nums[i]; 
        while(!numsStack.empty() && numsStack.top().first < currNum){
            pair<int,int> p = numsStack.top();
            numsStack.pop(); 

            answer[p.second] = currNum; 
        }

        numsStack.push({currNum,i}); 
    }
    for(int i = 0; i < N; i++){
        cout << answer[i] << ' '; 
    }
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt.txt", "r", stdin);
    Solve();
    return 0;

}