[백준/Python] 오큰수

📄 문제

백준
난이도 : Gold 4
문제 제목 : 오큰수

✏️ 풀이 1

import sys

n = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))
stack = []    # 오큰수 후보
answer = [-1] * n

for i in range(n - 1, -1, -1):
    while stack and stack[-1] <= lst[i]:
        stack.pop()
    answer[i] = stack[-1] if stack else -1
    stack.append(lst[i])

print(' '.join(map(str, answer)))

가장 오른쪽 수부터 for문을 돌면서 stack을 사용하여 오큰수를 찾는 풀이이다.

✅ 풀이 한줄 설명:
우선 stack이라는 빈 스택을 선언한 뒤, 오른쪽 수부터 삽입하면서 의미없는(앞으로 오큰수가 될 수 없는 수) 수들은 제거해나가는 방법이다. stack의 값과 현재 값을 비교하여 stack값이 더 크면 해당 값이 오큰수이다.
자세한 풀이는 아래 '✅ 풀이 자세한 설명'을 참고바란다.

✅ stack = [] : 가장 오른쪽 수부터 값을 저장하되, 앞으로 오큰수가 될 수 없는 것(왼쪽 수보다 작은 것)이 확인되면 pop() 해주어 스택에서 제거한다.

✅ 풀이 자세한 설명:

1. for문을 돌며 오른쪽 수부터 해당 수보다 큰 수가 stack에 존재하는지 확인한다.
   1.1. 해당 수보다 큰 수를 찾았다면, answer[i]에 찾은 수의 값을 저장한다.
   1.2. 해당 수보다 작은 수를 찾았다면, stack.pop()을 한 뒤 while문을 한 번 더 돈다.
2. while문을 통해 stack을 모두 확인하였음에도 해당 수보다 큰 수를 찾지 못한다면 오큰수가 존재하지 않는 것이니 answer[i]는 그대로 -1로 둔다.
3. 다음 수의 오큰수를 확인하러 가기 전에(이번 loop를 끝내기 전에), 현재 수도 다음 수의 오큰수가 될 수도 있으니, 현재 수를 stack에 넣어준다.

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Gold) '17298. 오큰수'
GitHub - [5강] 스택/응용문제 '17298. 오큰수'