24. 오등큰수(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 이다.

답:

from collections import Counter
from sys import stdin

n = int(stdin.readline())
nums = list(map(int, stdin.readline().split()))
nums_count = Counter(nums)
result = [-1] * n
stack = [0]

for i in range(1, n):
    while stack and nums_count[nums[stack[-1]]] < nums_count[nums[i]]:
            result[stack.pop()] = nums[i]
    stack.append(i)

print(*result)

먼저, 시간제한 때문에 stdin.readline()을 쓸 수밖에 없었다. 따라서 import문을 이용해서

시스템 리드라인을 가져오게 되었다.

이후 n을 입력받고, nums로 리스트화도 해줘야 한다.

(참고로 counter함수란 리스트에 있는 숫자들을 카운팅 해주는 함수이다.)

따라서 Counter로 숫자의 빈도수를 구해주고, (nums_count가 카운터 함수의 변수가 되어준다.)

이후 result를 n * -1의 형태로 미리 리스트를 할당한다. 그리고 스택이라는 배열을 만든다.

스택이라는 배열에는 0을 넣어준다. 그리고 이 스택은 크기를 비교해 주는 역할을 할 것이다.

그리고 while문을 돌면서 현재 숫자가 스택에 맨 위에 있는 값을 인덱스로 nums에 있는 숫자보다 빈도수가 높다면

result에 해당 숫자를 할당해 준다. 결국 최종 프린트는 result가 된다.

결론

이 문제는 앞에서 풀었던 오큰수에 대한 약간의 응용이 섞인 문제이다.

그래서 오큰수를 이해하고 있어야 한다.

(문제 이해도 어려움)