백준 17298 - 오큰수 (Python)

깃허브:

https://github.com/MSIQOC/BOJ/blob/master/b17298_%EC%98%A4%ED%81%B0%EC%88%98.py

 

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

17298번: 오큰수

 

https://reakwon.tistory.com/196

[스택] BOJ17298 오큰수 문제 풀이 및 전체 코드(C++)

 

위의 블로그를 참고해서 풀었다.

맨 오른쪽 숫자는 무조건 -1이기 때문에 오른쪽부터 왼쪽으로 가는 방식으로 접근한다.

i를 n-1부터 0까지 돌리고 스택의 top이 arr[i]보다 크면 그것이 그 숫자의 오등큰수가 된다. (작으면 스택에서 pop 시킨다.)

---

Python

 

#
# Created by MinSeo on 2022/02/06.
# Copyright ⓒ 2021 MinSeo Shin. All rights reserved.
#
n = int(input())
inp = list(map(int, input().split()))
stack = []
arr = [-1] * n
stack.append(inp[-1]) #제일 오른쪽 값 추가
for i in range(n-2, -1, -1):
    while stack and stack[-1] <= inp[i]:
        stack.pop()
    if stack:
        arr[i] = stack[-1]
    stack.append(inp[i])
 
for a in arr:
    print(a, end=' ')

여기에서 주의해야할 점은 while stack and stack[-1] <= inp[i]를 while stack[-1] <= inp[i] and stack로 순서를 바꾸면 index out of range 에러가 난다. (stack이 있는지를 검사하기 전에 stack[-1]에 들어가는거랑 stack이 없단걸 확인하고 바로 while문을 벗어나는 차이인 것 같다.)