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

파이썬에서 지원하는 heapq 모듈의 heap은 heapq.heappush() 할 때 배열이나 튜플이 들어가면 0번째 인덱스값을 기준으로 정렬하고, 똑같을 경우 자동으로 1번째 인덱스, 2번째 인덱스 순서대로 기준을 잡아 정렬해준다는 것을 알려준 문제

1차 시도

처음에는 이 사실을 모르고 heapq.heappush()함수에 배열이나 튜플이 들어가더라도 무조건 0번째 인덱스 기준으로만 정렬이 되는줄 알고 있었다. 그래서 너무 난잡하게 구현을 했었다.
일단 아이디어를 정리하자면

• 이중 우선순위 큐를 구현하기 위해 easy, hard 두 개의 힙을 사용했다.
  -> 이렇게 하면 O(1) 의 시간복잡도로 가장 쉬운문제, 가장 어려운 문제를 뽑아낼 수 있다.
• dif_set_max와 dif_set_min 두 개의 dictionary에 원소로 힙을 넣어 각 난이도별로 중복되는 문제들을 모았다.
  -> 이 때에는 easy, hard 힙에는 난이도를 기준으로 정렬은 되지만, 인덱스의 정렬 순서는 보장되지 않는다고 생각했다. 따라서 인덱스를 정렬하는 min, max 힙 두 개를 추가로 운용했었다.
• boj dictionary에는 문제의 존재여부와 난이도를 튜플형식으로 넣었다.
  -> 삭제된 문제는 False로 바꾸어 나중에 pop할 수 있도록 하고, 문제번호로 삭제할 때 난이도를 조회하여 dif_set_max와 dif_set_min에서 해당 문제번호를 삭제할 수 있도록 구현하기 위함이다.

이중 우선순위 큐를 두 개나 구현해서 사용하려니까 문제 추가 삭제 부분에서 예상치 못한 버그가 너무 많이 발생했고 알고리즘 자체도 너무 난잡했다.

import sys
import heapq

N = int(sys.stdin.readline())
boj = dict()
easy = list()
hard = list()
dif_set_max = dict()
dif_set_min = dict()

for i in range(N):
    b = list(map(int, sys.stdin.readline().split()))
    boj[b[0]] = [True, b[1]]
    heapq.heappush(easy, (b[1], b[0]))  # 난이도 , 인덱스
    heapq.heappush(hard, (-b[1], -b[0]))
    if b[1] in dif_set_max:                 # 딕셔너리에 난이도 인덱스로 접근해서 문제번호 쭉 가져올 수 있게 저장
        heapq.heappush(dif_set_max[b[1]], -b[0])
        heapq.heappush(dif_set_min[b[1]], b[0])
    else:
        dif_set_max[b[1]] = [-b[0]]
        dif_set_min[b[1]] = [b[0]]

# 명령어 저장
op = list()
M = int(sys.stdin.readline())
for j in range(M):
    op.append(list(sys.stdin.readline().split()))


for j in range(M):
    if op[j][0] == "recommend":
        par = int(op[j][1])
        if par == 1:
            while not boj[-hard[0][1]][0]:
                heapq.heappop(hard)
            temp = hard[0]
            while not boj[-dif_set_max[-temp[0]][0]][0]:
                heapq.heappop(dif_set_max[-temp[0]])
            print(-dif_set_max[-temp[0]][0])
        elif par == -1:
            while not boj[easy[0][1]][0]:
                heapq.heappop(easy)
            temp = easy[0]
            while not boj[dif_set_min[temp[0]][0]][0]:
                heapq.heappop(dif_set_min[temp[0]])
            print(dif_set_min[temp[0]][0])
    elif op[j][0] == "add":
        num, dif = int(op[j][1]), int(op[j][2])
        heapq.heappush(easy, (dif, num))
        heapq.heappush(hard, (-dif, -num))
        if dif in dif_set_max:
            heapq.heappush(dif_set_max[dif], -num)
            heapq.heappush(dif_set_min[dif], num)
        else:
            dif_set_max[dif] = [-num]
            dif_set_min[dif] = [num]
        boj[num] = [True, dif]
    elif op[j][0] == "solved":
        par = int(op[j][1])
        boj[par][0] = False
        dif = boj[par][1]
        temp = list()
        while -dif_set_max[dif][0] != par:
            temp.append(heapq.heappop(dif_set_max[dif]))
        heapq.heappop(dif_set_max[dif])
        while temp:
            heapq.heappush(dif_set_max[dif], temp.pop())
        while dif_set_min[dif][0] != par:
            temp.append(heapq.heappop(dif_set_min[dif]))
        heapq.heappop(dif_set_min[dif])
        while temp:
            heapq.heappush(dif_set_min[dif], temp.pop())

2차 시도

힙으로 한 번에 정렬할 수는 없을까 찾아보던 중, 힙에 배열이나 튜플이 들어가면 인덱스 순으로 자동정렬 해준다는 것을 알게 되었다.
이러면 굳이 이중 우선순위 큐를 두 개 만들 필요 없이 하나만 구현 한 후 거기서 난이도, 번호 순서대로 정렬을 하도록 만들면 되었다.

자료구조 초기화
easy, hard 두 개의 힙만 만든 다음, hard에선 가장 어려운 난이도, 가장 높은 번호의 문제를 출력해야 했으므로 둘 다 최대힙으로 구현하기 위해 마이너스를 붙여주었다.
easy는 가장 쉬운 난이도, 가장 작은 번호 순으로 출력해야 했으므로 둘 다 최소힙으로 구현하였다.
boj는 인덱스를 통해 O(1)의 시간복잡도로 문제정보에 접근하기 위해 딕셔너리로 만들었으며, 문제의 존재여부와 난이도 정보를 가지고 있다.

문제 추가 삭제
문제 추가 시에는 초기화와 같은 알고리즘으로 추가해 주었고 문제 삭제 시에는 boj 에서 인덱스로 접근 후 (딕셔너리 이므로 O(1)의 시간복잡도로 바로 접근 가능하다.) 문제의 존재여부만 False로 바꾸어 주었다.

추천문제 출력 및 힙에서 문제삭제
아직 힙에서 문제가 삭제는 되지 않았으므로 recommend에서 문제를 뽑을 때 boj 에서 문제 번호를 조회하여 존재하는 문제인지, 난이도가 변경되지는 않았는지를 판단하여 만족하지 않을 경우 heappop을 하여 실제로 삭제를 진행했다.

import sys
import heapq

N = int(sys.stdin.readline())
boj = dict()
easy = list()
hard = list()

for i in range(N):
    b = list(map(int, sys.stdin.readline().split()))
    boj[b[0]] = [True, b[1]]
    heapq.heappush(easy, (b[1], b[0]))  # 난이도 , 인덱스
    heapq.heappush(hard, (-b[1], -b[0]))

# 명령어 저장
op = list()
M = int(sys.stdin.readline())
for j in range(M):
    op.append(list(sys.stdin.readline().split()))


for j in range(M):
    if op[j][0] == "recommend":
        par = int(op[j][1])
        if par == 1:
            while not boj[-hard[0][1]][0] or boj[-hard[0][1]][1] != -hard[0][0]:
                heapq.heappop(hard)
            temp = hard[0]
            print(-temp[1])
        elif par == -1:
            while not boj[easy[0][1]][0] or boj[easy[0][1]][1] != easy[0][0]:
                heapq.heappop(easy)
            temp = easy[0]
            print(temp[1])
    elif op[j][0] == "add":
        num, dif = int(op[j][1]), int(op[j][2])
        heapq.heappush(easy, (dif, num))
        heapq.heappush(hard, (-dif, -num))
        boj[num] = [True, dif]
    elif op[j][0] == "solved":
        par = int(op[j][1])
        boj[par][0] = False

힙에서 리스트의 인덱스를 기준으로 차례대로 정렬해주는 거는 꼭 기억해야겠다. 이걸 몰라서 너무 많은 시간을 삽질한것 같다.