[백준 17298] 오큰수

문제 풀이

 

오큰수를 다시 정리하면 다음과 같다.

나보다 크며, 오른쪽 중에서는 가장 작은 수여야 한다.

[3 5 2 7]에서 내가 5라고 가정하면, 오큰수는 7이다.

 

단순하게 완전 탐색으로 돌리게 되면 O(N^2)이 걸리게 된다.

N이 100만이기 때문에 시간 초과가 발생하므로 조금 더 빠르게 오큰수를 찾는 방법이 필요하다.

 

이런 문제는 스택 자료구조를 사용하면 O(N)으로 해결할 수 있게 된다.

스택은 아래와 같은 방법으로 동작한다.

1) 스택이 비어있으면 -1 (오큰수가 없으므로) 처리하고, 스택에 push 한다. 푸시하는 이유는 다음의 오큰수에 해당될 수 있으므로

2) 스택이 비어있지 않으면,

입력된 arr[i] < stack의 top이면? stack의 top이 해당 오큰수를 뜻하고,

>= 이면 <가 나올때까지 스택에서 계속해서 오큰수를 pop 하면서 찾는다.

만약에 찾게 된다면 해당 수가 오큰수이며, 입력된 arr[i]를 스택에 push 한다.

못 찾게 된다면 해당 수에 오큰수가 존재하지 않으므로 -1이다.

 

입력된 배열의 역순으로 하나씩 확인하면서 스택을 응용하면 된다.

 

문제에서 주어진 예시로 다시 확인해보자.

입력된 수	스택 자료구조	오큰수 배열
7	empty
	7	[0, 0, 0, -1]
2	7
	7 2	[0, 0, 7, -1]
5	7 2
	7 5	[0, 7, 7, -1]
3	7 5
	7 5 3	[5, 7, 7, -1]

입력된 수 : 7

현재 스택이 비어있기 때문에 오큰수는 -1이며, 스택에 7을 삽입하면 된다.

 

입력된 수 : 2

현재 스택의 top(7)이 2보다 크므로 2의 오큰수는 7이며, 스택에 2를 삽입한다.

 

입력된 수 : 5

현재 스택의 top(2)보다 5가 더 크므로 스택에서 하나를 뺀다.

현재 스택의 top(7)이 5보다 크므로 5의 오큰수는 7이며, 스택에 5를 삽입한다.

 

입력된 수 : 3

현재 스택의 top(5)이 3보다 크므로 3의 오큰수는 5이며, 스택에 3을 삽입한다.

 

소스 코드

 

#include <iostream>
#include <stack>

using namespace std;

int N;
int arr[1000001];
int ans[1000001];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> arr[i];
    
    stack<int> st;
    for(int i = N - 1; i >= 0; i--)
    {
        while(!st.empty() && st.top() <= arr[i])
            st.pop();
        
        if(!st.empty())
        {
            ans[i] = st.top();
        }
        else
            ans[i] = -1;
        
        st.push(arr[i]);
    }
    
    for(int i = 0; i < N; i++)
        cout << ans[i] << ' ';
    
    return 0;
}