크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
위 풀이대로 진행하였고 결과는 잘 통과한다.
import sys
input = sys.stdin.readline
N = int(input().rstrip())
sequence = list(map(int, input().rstrip().split()))
answer = [-1] * N
stack = []
for i in range(N):
while stack and sequence[stack[-1]] < sequence[i]:
top = stack.pop()
answer[top] = sequence[i]
stack.append(i)
print(" ".join(map(str, answer)))
스택에 대한 이해도가 조금은 생긴 것 같다. 확실히 머리속에 정리된 개념을 넣고 그 안에서 문제의 난이도를 조금씩 높이는 방법이 괜찮은 것 같다. 파이썬 알고리즘 인터뷰 책도 도움이 많이 되고 있다. 이렇게 계속 공부해나가면 될 듯 하다.
아침에 운동갔다와서 바로 공부를 들어가는게 어렵다. 공부를 바로 할 수 있게 도와주는 루틴을 만드는게 좋을 것 같다. 한 번 생각해보자