[백준]17298번 오큰수 - C++

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

17298번: 오큰수

---

 

배열을 순회하면서 스택에 {값,인덱스}를 삽입한다. 이때 자신보다 작은 수들은 오큰수가 자신이 될 것이기 때문에 pop을 해주면서 오큰수를 저장해준다. 이 다음 자신을 스택에 푸쉬 하는 과정을 반복한다면 문제를 쉽게 풀 수 있다.

#include<iostream>
#include<stack>
#include<cstring>
using namespace std;

int N;
int arr[1000001];
int dp[1000001];
typedef pair<int, int> point;
stack <point> s;
int main (){
    cin >> N;
    for(int i = 0 ; i < N ; i++)
        cin >> arr[i];
    memset(dp,-1,sizeof(dp));
    for(int i = 0 ; i < N ; i++){
        if(!s.empty()){
            if(s.top().first < arr[i]){
                while(!s.empty() && s.top().first < arr[i]){
                    dp[s.top().second] = arr[i];
                    s.pop();
                }
            }
            s.push(make_pair(arr[i],i));
        }
        else
            s.push(make_pair(arr[i],i));
    }
    for(int i = 0 ; i < N;i++)
        cout << dp[i] << " ";
    return 0;
}

---

처음에는 배열의 뒤부분부터 자신 보다 큰 수를 만날때까지 dp 배열을 채워나가는 방식을 사용했으나 오름차순으로 정렬된 배열이 들어올 경우 O(N^2)의 시간이 걸리기 때문에 시간초과가 나게된다. 그래서 dp 배열로는 풀 수 없을 것 같아 고민을 해보았지만 생각이 나지 않았다. 그래서 알고리즘 분류를 슬쩍 보았더니 스택이라는 것을 보자마자 아차 싶었다. 스택이라는 것을 본 뒤에 아이디어가 바로 생각나는 간단한 문제였던 것이다. 평소에 어떠한 알고리즘으로 풀지를 생각하면서 그래프, dp, 그리디 이정도를 생각하고 풀었는데 단순 자료구조 문제를 풀지 못했던 것이다! 앞으로는 조금 더 넓은 시야를 가질 수 있을 것 같다.