[백준] 17299: 오등큰수 (python 파이썬)

해당 문제는 이전에 풀었던 오큰수(17298)과 비슷한 문제다. 단지 while문의 조건만 바꾸어주면 된다. 알고리즘은 다음과 같다.

• 결과를 담을 리스트를 선언한다. 이때 원소들은 모두 -1을 가진다. (result list)
• 각 원소가 몇 번 나왔는지 카운트한 숫자를 담은 dict를 선언한다. (count_dict) 단, 현재 코드에서는 defaultdict를 사용했지만, 그냥 (모든 원소가 0인) 100만까지의 숫자를 담을 수 있는 리스트를 선언해도 된다.
• stack은 아직 자기보다 많이 나온 수를 찾지 못한 원소들의 인덱스를 담는다. 0번째 인덱스부터 탐색해야하므로 0을 담고 시작한다.
• 반복문을 통해 1번~n-1번 인덱스까지 탐색한다. (탐색 중인 원소를 current_value[=array[i]]라고 하자.)
• stack에 남아있는 원소가 있고(자기보다 큰 수를 찾지 못한 원소가 있고), 그 원소들 중 가장 오른쪽의 원소와 current_value를 비교했을 때 current_value의 나온 횟수가 더 크다면, stack에서 가장 오른쪽의 원소를 빼내고, 해당 원소의 NGF값은 current_value로 설정한다. 

코드는 다음과 같다.

import sys
from collections import defaultdict

input = sys.stdin.readline

n = int(input())
array = list(map(int, input().split()))
count_dict = defaultdict(int)

for i in array:
    count_dict[i] += 1
    
result = [-1 for _ in range(n)]
stack = [0]

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

print(*result)

---

오등큰수: https://www.acmicpc.net/problem/17299

오큰수: https://www.acmicpc.net/problem/17298