17298번 - 오큰수

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

17298번: 오큰수

이 문제를 보고 처음 생각이 난 풀이 방법은 '각 원소에 대해 오른쪽에 있는 원소를 하나씩 살펴보며 더 큰지 검사하는 방법'이었다. 하지만 이는 최악의 경우인 '9 8 7 6 5 4 3 2 1'의 경우 모두 -1이 출력되는데, 각각의 원소에 대해 더 큰 값이 있는지 살펴보기 위해 리스트 전체를 뒤지는 상황이 생긴다. 이러한 접근 방식은 무조건 시간 초과가 발생하기 때문에 올바른 방법이 아니다.

 

그렇게 생각한 두 번째 방법은 오른쪽 원소부터 검사하는 것이다. 

# 오큰수
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
comp = deque()
answer = [0 for _ in range(N)]

for i in range(N-1, -1, -1):
    while comp and A[i] >= comp[0]:
        comp.popleft()
    if comp:
        answer[i] = str(comp[0])
    else:
        answer[i] = '-1'
    comp.appendleft(A[i])

print(' '.join(answer))

comp라는 덱을 선언한다. 이 덱은 A라는 리스트의 오른쪽 끝 원소부터 차근차근 검사하며 최댓값을 저장한다. 만약 A[i]번째를 검사할 때 comp가 비어있지 않고 comp[0] 값보다 더 크다면 / 오른쪽 리스트에 해당 값(A[i])보다 크다는 뜻이 아니기 때문에 popleft()를 진행한다. 그렇게 while문이 종료되면 comp[0]이 A[i]보다 크거나, comp가 비어있는 두 가지 경우가 남는다.

더 크다면 comp[0]을 answer에 넣고, 비어있다면 -1을 넣어준다. 

그리고 A[i]를 comp에 넣어주면서 과정은 끝난다. 

 

이 방법에서 가장 중요한 접근 방식은 아래와 같다.

1. 오른쪽 끝에서부터 접근한다.

2. A[i]보다 작은 값이 comp에 있다면 앞에서부터 지워준다.

 

추가로 comp라는 덱을 스택으로 선언해도 상관없다. popleft와 appendleft만을 사용하고 있기 때문이다.