[백준/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 이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

예제 입력 1

7
1 1 2 3 4 2 1

예제 출력 1

-1 -1 1 2 2 1 -1

풀이 방법
N의 범위가 1000000이기 때문에 최대 nlogn의 시간복잡도를 가져야 한다
마지막 원소는 항상 -1의 값을 가지고 현재 값보다 오른쪽에 위치하는 값들 중에 현재 값보다는 크면서도 가장 왼쪽에 위치하는 값을 찾아야하기 때문에 heap 구조를 떠올렸다

1. 만약 heap의 길이가 0이라면 ngf에 -1을 갱신한다
2. 길이가 0이 아니면 스택에서 pop을 한 값과 heap의 top에 위치하는 값을 비교한다
3. heap의 top이 현재 값보다 크다면 현재 값보다 오른쪽에 존재하는 수들 중 가장 작은 값이기 때문에 ngf를 갱신해준다
4. 만약 현재 값이 heap의 top 보다 작거나 같다면 큰 값이 나올때 까지 heap에 있는 수들을 pop한다
5. 2번 과정과 3번 과정이 끝난다면 현재 값을 heap에 push해준다
6. 모든 수를 탐색했을 때 값이 갱신되지 않은 수가 있다면(남은 수들보다 현재 값이 크거나 같은 경우) -1로 바꿔준다

코드

import sys, heapq
from collections import deque

n = int(sys.stdin.readline())
q = deque(map(int, sys.stdin.readline().split()))

cnt_dict = dict()

for elem in q:
    if not cnt_dict.get(elem):
        cnt_dict[elem] = 1
    else:
        cnt_dict[elem] += 1

ngf = [0]*len(q)


# 최소 힙을 이용하기
# 맨 뒤 원소부터 pop해서 힙에 넣기 전에 top 값이 자기보다 크면 ngf 갱신
# 자신보다 값이 작거나 같으면 top을 pop하기
# 이후 heap에 값 넣기

heap = []
while q:
    x = q.pop()
    if len(heap) == 0 :
        ngf[len(q)] = -1
    while len(heap) and heap[0][0] <= cnt_dict[x]:
        heapq.heappop(heap)
    if len(heap) and heap[0][0] > cnt_dict[x]:
        ngf[len(q)] = heap[0][1]
    heapq.heappush(heap, (cnt_dict[x],x))

for i in range(n):
    if ngf[i] == 0:
        ngf[i] = -1
print(*ngf)