[baekjoon] 백준 17298번(파이썬): 오큰수

문제

17298번: 오큰수

알고리즘

- 오큰수를 인덱스로 확인한다.

- 오큰수가 아니면 오큰수 리스트에 오큰수가 아닌 인덱스를 입력받는다.

- 비교한 수가 오큰수이면 해당 값을 팝하고 그 자리에 오큰수를 입력한다.

코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

cnt = [0] # 오큰수를 0번째 인덱스부터 확인한다.
res = [-1] * n

for i in range(1, n):

    # 오큰수가 있는지 확인한다.
    while cnt and a[cnt[-1]] < a[i]:
        # 오큰수이면 비교한 값을 팝하고 오큰수를 입력 받는다.
        # 위 과정을 오큰수 리스트가 사라질 때까지 한다.
        res[cnt.pop()] = a[i]

    # 오큰수를 비교할 인덱스를 추가한다.
    cnt.append(i)

print(*res)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법