오늘의 문제- boj-17298

문제

크기가 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이다.

풀이

1. 스택에 수를 넣는다.
2. 스택의 수와 지금 수를 비교하여 지금 수가 더 크다면 스택을 pop 해주고 지금 수를 스택의 인덱스에 넣어준다.
3. 크지 않다면 스택에 지금 수를 넣어주고 순회를 계속한다.
4. 마지막까지 순회를 마쳤을 때 오큰수가 없다면 -1을 넣어준다. (-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)))

피드백

스택에 대한 이해도가 조금은 생긴 것 같다. 확실히 머리속에 정리된 개념을 넣고 그 안에서 문제의 난이도를 조금씩 높이는 방법이 괜찮은 것 같다. 파이썬 알고리즘 인터뷰 책도 도움이 많이 되고 있다. 이렇게 계속 공부해나가면 될 듯 하다.

아침에 운동갔다와서 바로 공부를 들어가는게 어렵다. 공부를 바로 할 수 있게 도와주는 루틴을 만드는게 좋을 것 같다. 한 번 생각해보자