[Python] 백준 17299번 - 오등큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

내 코드

import sys

N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))
count = [0] * 1000001
stack = []
ans = [-1] * N
for i in seq:
    count[i] += 1

for i in range(N):
    while stack and count[seq[i]] > count[seq[stack[-1]]]:
        ans[stack.pop()] = seq[i]
    stack.append(i)
print(*ans)

 

오큰수 문제와 비슷한 방식이다. stack에 index를 저장하고 큰 값이 나오면 stack에 이미 넣은 index를 이용하여 pop하면서 오등큰수를 만든다.

인덱스 번호를 이용해 입력된 값의 중복 숫자를 카운트한다. (숫자를 인덱스 번호로 사용해서 + 연산)

1,000,000개의 입력을 고려하여 0으로 이루어져 있는 1,000,000 크기의 count 리스트를 생성한다.

현재 peek하고 있는 값이 stack의 top의 인덱스 count보다 큰 값일 시에 pop하고 ans[pop된 인덱스]에 저장한다.

(무슨 말인지 나도 모르겠네;;)