[BOJ:17298] 오큰수

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

Note

수열이 있을 때 각 원소, A(i)의 오큰수는 각 원소, A(i)보다 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

처음 생각한 방식은 2중 for문을 돌면서 각 원소보다 큰 원소를 찾으면 내부 for문을 중단하는 방식이다. 하지만 이때 최악의 경우 O(N^2)이 나온다. 최악의 경우가 나오는 경우는 처음 원소부터 모두 감소하는 형태의 수열이 존재하는 경우 모두 오큰수가 존재하지 않아서 모든 수열이 -1의 오큰수를 갖는 경우이다.

하지만 스택을 이용하면 O(N)의 시간복잡도를 가질 수 있다.

스택을 이용한 오큰수 찾기 알고리즘은 다음과 같다.

0인덱스 부터 n-1인덱스 까지 선형적으로 탐색을 하면서 아직 오큰수를 찾지 못하면 스택에 담는다. 그리고 스택에서 가장 꼭대기에 있는 수와 현재 수를 비교하여 오큰수면 오큰수를 기록하고 스택에서 제거한다.

스택을 사용하는 이유는 가장 최근에 넣은 수를 찾는 자료구조 이기때문이다.

오른쪽이면서 가장 왼쪽은 사실 바로 우측 옆이다. 그런데 이 수가 나보다 크지 않다면 오큰수는 바로 다음 수에서 찾아야 한다. 이렇게 바로 직전 수와 비교하면서 오큰수를 확인하는 작업을 하기 위해서는 가장 최근에 넣은 데이터를 쉽게 찾을 수 있는 스택을 이용하면 된다.

2중 for문과 스택의 차이점은 2중 for문이 내가 나의 오큰수를 찾아 나서는 거라면 스택은 반대로 생각하면 된다. 다시 말해서 오큰수가 원소를 찾는 방식이다. 현재 오큰수 후보가 바로 왼쪽수 오큰수인지 확인하고 아니면 일단 스택에 기록해두고 또 다음 원소에서 찾는 것이다.

Code

import sys
input = sys.stdin.readline

sequence_length = int(input())
sequence = list(map(int,input().split()))
answer = [-1]*sequence_length

stack = [] #아직 오큰수를 찾지 못한 수열의 원소의 인덱스 값을 저장하는 스택
for sub_NGE_index in range(sequence_length): # sub_NGE_index : 오큰수 후보
    while stack and sequence[stack[-1]] < sequence[sub_NGE_index]:
        answer[stack[-1]] = sequence[sub_NGE_index]
        stack.pop()
    stack.append(sub_NGE_index)

print(*answer)