[백준] 1713 - 후보 추천하기

백준 1713번 후보 추천하기

 

✅문제 링크 : https://www.acmicpc.net/problem/1713

 

이 문제는 운영체제에서 프로세스를 정렬할 때 LRU(Least Recently Used) 와 우선순위 큐를 결합한 형태의 정렬과 가깝다. 따라서 우선순위 큐를 가장 쉽게 구현할 수 있는 heap를 사용하였다. 

heap의 요소로, 후보의 추천 횟수와 후보를 list로 묶어 넣고, is_in(x) 함수를 통해 x 후보가 힙에 있으면 해당 횟수를 1번 증가시키는 방법으로 문제를 해결하였다. 

 

그러나 4% 쯤에서 오답이 나오자, 힙을 출력해봤더니, 가장 오래된 사진을 heappop으로 빼낼 때 heap이 같은 횟수라도 오래된 순서로 정렬되어있지 않다는 문제가 발생했다. 그리고 정렬 방식도 일관되지 못했다. 

우선 파이썬의 heapq에서는 리스트 요소를 넣으면 리스트의 첫 번째, 두 번째, ... 순으로 우선순위를 결정하므로, 후보가 추천된 순서 i 를 list의 2번째 요소로 넣어서, 추천 횟수 다음에는 추천받은 순서가 오래된 순으로 정렬되도록 하였다. 이렇게 했을 때 오래된 순으로 정렬되기는 하지만 여전히 오답이 났는데, 그 이유는 is_in 함수에 있었다.

is_in(x) 함수에서는 힙을 만드는 리스트 cand에서, cand[i][0] += 1 로 이미 있는 후보의 추천 횟수를 정렬하는데, 이렇게만 해놓으면 heap은 내부적으로 자동 정렬을 하지 않기 때문에 반드시 heapq.heapify(cand)를 한 번 실행해 줘야 한다는 것이다. heappop이나 heappush, heapify 함수를 실행했을 때만 heap 재정렬을 하므로 값을 갱신했을 때 반드시 해당 함수를 호출해주어야 한다. 

따라서 그 코드까지 추가한 후 정답을 낼 수 있었다. 코드는 아래와 같다. 

 

import heapq
import sys

input = sys.stdin.readline
n=int(input())
t=int(input())

lst=list(map(int,input().split(' ')))

# heap 리스트 cand
cand=[]

# 현재 사진이 걸린 후보의 인원 수
current=0

# heap에 x 후보가 있는지, 있다면 추천수를 1만큼 올리고 다시 heap 정렬
def is_in(x):
    for i in range(current):
        if cand[i][2]==x:
            cand[i][0]+=1
            
            ########## 이 부분에서 막혔음 ##########
            heapq.heapify(cand)
            ######################################
            
            return True
    return False

# 후보 추천 시작
for i in range(t):
	# 이미 후보가 있다면 is_in 함수만 실행 후 다른 작업 X
    for_x=is_in(lst[i])
    
    # 사진에 걸리지 않은 새로운 후보가 추천되었다면
    if not for_x:
    	# 사진틀이 남은 경우 heap에 추천 횟수 1, 추천 시간 i, 후보 순으로 list 만들어서 heappush
        if current<n:
            heapq.heappush(cand, [1,i,lst[i]])
            current+=1
        # 사진들이 꽉 차 있는 경우 heappop으로 후보를 제거하고, heappush
        else:
            heapq.heappop(cand)
            heapq.heappush(cand, [1,i,lst[i]])

# 각 요소의 3번째, 후보 번호 순으로 정렬 후 후보 출력
cand.sort(key=lambda x : (x[2]))
for i in range(current):
    print(cand[i][2], end=' ')