백준 17299 오등큰수 파이썬 문제 설명 O heapq사용

https://www.acmicpc.net/problem/17299

17299번: 오등큰수

문제 해석부터가 어려웠던 문제였다.

뒤에 해석까지 있었으면 더 이해하기 편했을거 같다.

A4가 왜 2가 되냐면 A[4~n] 까지 나온 수를 보면 3, 4, 2, 1이 나왔음을 알 수 있다. (굵은 숫자가 비교 값)

차례대로 1, 1, 2, 3인데  비교 대상은 1이다. 따라서 1보다 큰 수 중에 가장 왼쪽에 있는 값(비교 값 보다 큰 수가 처음 나온 위치의 수 )을 해줘야하는데 그 수가 2번나온 2여서 A4는 2가 된다.

코드는 heapq을 사용해 적절히 heapq값을 갱신 시킨 뒤 배열 뒤에서 부터 탐색하는 형식으로 만들었다.

 

import heapq
n = int(input())
s = list(map(int,input().split()))
re = [-1]*n
dic = {}
for i in s:#몇번 나왔는지 세어주는 작업
    try:
        dic[i]+=1
    except:
        dic[i]=1
h = []
for i in range(n-1,-1,-1):
    while h:
        if len(h)!=1 and h[0][0]==dic[s[i]]: #만약에 h[0][0]과 dic[s[i]]와 같은데 h의 길이가 1이면
        					#-1을 반환해야해서 len(h)!=1이여야한다.
            a = heapq.heappop(h)
            re[i]=a[1]
        elif h[0][0]>dic[s[i]]:#문제 조건에 맞게 dic[s[i]]보다 큰 수중 가장 왼쪽인 수이니
            re[i] = h[0][1] #저장해주고 break
            break
        else:#새롭게 탐색된 dic[s[i]]가 h[0][0]보다 크니 지워준다.
            heapq.heappop(h)
    heapq.heappush(h,(dic[s[i]],s[i]))#h에 지금 s[i]가 나온 횟수와 s[i]를 저장해준다.
print(*re)