BOJ 17298. 오큰수 (Stack)

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

17298번: 오큰수

이번 문제는 스택을 이용하면 풀기 쉽다.

예제 1번에서 3, 5, 2 ,7의 수열로 예시를 들어보자.

 

처음의 경우에는 비교할 대상이 없기때문에 스택에 숫자의 인덱스를 넣자

- 스택 : [0, ]

그 다음은 이제 5인데(현재 인덱스는 1) 스택 인덱스에 해당되는 배열 수의 값이 현재 숫자보다 크면 결과 리스트에 집어 넣는다. (오른쪽에 있는 큰 수들 중에서 가장 왼쪽을 고르는 문제이기때문)

- 결과 리스트 : [5, ]

- 스택 : [1, ]

5랑 2 비교하면 (현재 인덱스) 2는 작기때문에 2는 결과값에 반영할 수가 없다. 그러므로 스택에 현재 인덱스를 넣고 다음 인덱스로 넘긴다.

- 스택 : [1, 2]

- 결과 리스트 [5, ]

7은 2보다 크고 오른쪽에 있기 때문에 2에 해당하는 인덱스 2번에 7을 넣게 되고 2는 pop하게 되며 1에 대해서도 같은 방법으로 적용하면 결과 리스트는 아래와 같다

- 결과 리스트 [5, 7, 7, ]

- 스택 : [3]

마지막 7의 경우에는 인덱스가 하나가 남아있게 되는데 이는 최종 출력전에 스택이 비어있을 때까지 -1로 결과 리스트에 집어 넣으면 된다.

- 스택 : []

- 결과 리스트 : [5, 7, 7, -1]

 

n = int(input())

result = [0] * n
ms = []
num_list = list(map(int, input().split()))

for i in range(n):
    
    #스택이 비어있지 않고, 현재 수가 스택의 인덱스에 해당하는 수보다 클때까지
    while ms and num_list[ms[-1]] < num_list[i]:
        result[ms.pop()] = num_list[i]
    ms.append(i)
    
while ms:
    result[ms.pop()] = -1    

print(*result)