백준 19298번: 오큰수 (Python)

접근

당연하게도 for문을 돌려서 더 큰 수가 나올 때까지 탐색하면 시간 초과되게 된다. 스택 문제 답게 스택을 써서 풀어보았다.

처음에 빈 stack 리스트를 만들고 주어진 수 배열의 첫 숫자부터 탐색하게 된다. stack에는 주어진 수 배열의 index를 저장하게 되는데, 탐색 중에 stack이 비어있거나, stack의 top에 해당하는 숫자가 탐색중인 숫자보다 작으면 해당 숫자를 ans라는 새로운 리스트에 저장하게 된다.

for문을 통해 탐색하게 되는데 예시 입력1에서 i = 0 일 때부터 확인해보면 다음과 같다.

# i = 0 일 때, stack이 비어있으므로 0을 push 해준다.
stack = [0]

# i = 1 일 때, stack의 top에 해당하는 수 m[0] = 3 이고 m[i] = 5이므로 m[i]가 더 크다.
# 이는 m[0] = 3 보다 크면서 가장 왼쪽에 있는 숫자는 m[1] = 5라는 의미이다. 그러므로 이 숫자를 ans에 저장.
# 이후 이 i를 stack에 push
ans[stack.pop()] = m[1]
ans = [5]
stack = [1]

# i = 2 일 때, stack의 top에 해당하는 수 m[1] = 5 이고 m[i] = 2 이므로 m[1]이 더 크다. pass
# i를 stack에 push
ans = [5]
stack = [1, 2]

# i = 3 일 때, stack의 top에 해당하는 수 m[1] = 5 이고 m[i] = 7이므로 m[i]가 더 크다.
# 이 숫자를 stack이 없어질 때까지 ans에 저장. stack에 지금 요소가 2개 있기 때문에 ans의 1번, 2번요소에 같은 수가 들어가게 된다.
ans[stack.pop()] = m[3]
ans[stack.pop()] = m[3]
ans = [5, 7, 7]
stack = [3]

이와 같은 방법으로 반복하면 문제를 해결할 수 있다. 코드를 보면 좀더 이해하기 쉽다.

코드

import sys

n = int(sys.stdin.readline())
m = list(map(int, sys.stdin.readline().split()))
stack = []
ans = [-1 for _ in range(n)]
for i in range(n):
    while stack and m[stack[-1]] < m[i]:  # 스택이 비어있지 않으면서, 다음 수가 해당 수보다 크면
        ans[stack.pop()] = m[i]  # 현재 수에 해당하는 index에 다음 수 집어넣기
    stack.append(i)
print(*ans)

더 생각해 볼 것?

머리로는 이해했으나 글로 설명하기가 너무 어렵다고 느껴졌다. 심지어 지금 설명된 내용도 이해하기 쉽지 않다고 느껴진다. 아직 이해가 완벽하지 않은 것인지.. 좀 더 공부가 필요한 것 같다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!