[알고리즘] BOJ 21939 문제 추천 시스템 Version 1 #Python

[BOJ] 21939 문제 추천 시스템 Version 1 바로가기

📍 문제

tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다.

깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다.

만들려고 하는 명령어는 총 3가지가 있다. 아래 표는 각 명령어에 대한 설명이다.

명령어 recommend는 추천 문제 리스트에 문제가 하나 이상 있을 때만 주어진다.

명령어 solved는 추천 문제 리스트에 문제 번호가 하나 이상 있을 때만 주어진다.

위 명령어들을 수행하는 추천 시스템을 만들어보자.

---

📍 입력

첫 번째 줄에 추천 문제 리스트에 있는 문제의 개수 $N$ 가 주어진다.

두 번째 줄부터 $N + 1$ 줄까지 문제 번호 $P$와 난이도 $L$가 공백으로 구분되어 주어진다.

 $N + 2$줄은 입력될 명령문의 개수 $M$이 주어진다.

그 다음줄부터 $M$개의 위에서 설명한 명령문이 입력된다.

---

📍 출력

recommend 명령이 주어질 때마다 문제 번호를 한 줄씩 출력한다. 최소 한번의 recommend 명령어가 들어온다.

---

📍 풀이

💡 고찰

• add P L 명령어는 문제 난이도(L)를 기준으로 이미 정렬되어 있는 문제들 사이에 새로운 문제를 추가하는 방식을 적용해야 했고, 이에 최적화된 자료구조는 힙(Heap) 자료구조이다.
• recommend x 명령어는 문제 난이도(L)를 기준으로 가장 큰 값과, 가장 작은 값을 찾을 수 있어야 했고, 이를 위해서 최소힙(minHeap)과 최대힙(maxHeap) 2개의 자료구조를 사용해야 한다는 것을 알 수 있다.
• solved P 명령어는 문제 번호(P)에 해당하는 문제를 각 힙에서 제거해 주어야 한다.
• ❗️ 문제는 각 힙에서 문제 번호(P)에 해당하는 문제를 제거하면 힙 자료구조의 규칙에 문제가 발생해서 힙 자료구조의 의미가 사라진다.
• 이 문제를 어떻게 해결할지 많은 고민을 했고, 해결책은 recommend x 명령어를 받았을 때 현재 문제 난이도(L)가 가장 작은 값 혹은 가장 큰 값이 이미 삭제된 문제라면 heappop 을 수행하여 필요할 때마다 제거하는 방식을 적용하였다.

📌 문제 풀이

✏️ 1. 힙 자료구조 초기화

# [1] 최대힙, 최소힙 초기화
for p, l in PL:
    heappush(minHeap,(l,p))
    heappush(maxHeap,(-l,-p))

• 최소힙은 문제 난이도(l)와 문제 번호(p)를 그대로 원소를 추가한다.
• 최대힙은 문제 난이도(l)와 문제 번호(p)에 - 를 적용하여 원소를 추가한다.

✏️ 2. 문제 번호 출력

# [3] 문제 번호 출력
if command[0] == "recommend":
    # [3-1] 가장 어려운 문제
    if command[1] == "1":
        while solved[abs(maxHeap[0][1])] != 0:
            solved[abs(maxHeap[0][1])] -= 1
            heappop(maxHeap)
        print(-maxHeap[0][1])
    # [3-2] 가장 어려운 문제
    else:
        while solved[minHeap[0][1]] != 0:
            solved[minHeap[0][1]] -= 1
            heappop(minHeap)
        print(minHeap[0][1])

• command 의 값이 recommend 1 인 경우 최대 힙(maxHeap)에서 문제 난이도(maxHeap[0][1])가 가장 어려운 문제를 검색하고, 해당 문제가 이미 푼 문제(solved)라면 해당 문제를 제거(heappop())한다.
• 문제 제거 연산이 종료된 후 풀지 않은 문제 중에서 난이도가 가장 어려운 문제의 문제 번호(maxHeap[0][1])를 출력한다.
• command 의 값이 recommend -1 인 경우 최소 힙(minHeap)에서 문제 난이도(minHeap[0][1])가 가장 쉬운 문제를 검색하고, 해당 문제가 이미 푼 문제(solved)라면 해당 문제를 제거(heappop())한다.
• 문제 제거 연산이 종료된 후 풀지 않은 문제 중에서 난이도가 가장 쉬운 문제의 문제 번호(minHeap[0][1])를 출력한다.

✏️ 3. 문제 추가

# [4] 문제 추가
elif command[0] == "add":
    p, l = int(command[1]), int(command[2])
    heappush(minHeap,(l,p))
    heappush(maxHeap,(-l,-p))

• command 의 값이 add P L 인 경우 최소 힙(minHeap)과 최대 힙(maxHeap)에 heappush() 를 통해 문제를 추가한다.

✏️ 4. 문제 제거

# [5] 문제 제거
elif command[0] == "solved":
    solved[int(command[1])] += 1

• command 의 값이 solved P 인 경우 문제 번호(P)에 해당하는 문제를 풀었다는 것을 구별하기 위해 defaultdict(int) 자료구조를 이용하여 생성한 solved 딕셔너리에 문제 번호(P)에 해당하는 값을 1 증가시킨다.
• defaultdict(int) 자료 구조의 값을 int 로 설정한 이유는 문제 난이도가 다른 같은 번호의 문제가 2개 이상 존재하는 경우를 고려하였다.

✍ 코드

from sys import stdin
from heapq import heappush, heappop
from collections import defaultdict

def solution(N, PL, M, commands):

    minHeap, maxHeap = [], []
    solved = defaultdict(int)

    # [1] 최대힙, 최소힙 초기화
    for p, l in PL:
        heappush(minHeap,(l,p))
        heappush(maxHeap,(-l,-p))

    # [2] 명령어 수행
    for command in commands:
        command = command.split()
        # [3] 문제 번호 출력
        if command[0] == "recommend":
            # [3-1] 가장 어려운 문제
            if command[1] == "1":
                while solved[abs(maxHeap[0][1])] != 0:
                    solved[abs(maxHeap[0][1])] -= 1
                    heappop(maxHeap)
                print(-maxHeap[0][1])
            # [3-2] 가장 어려운 문제
            else:
                while solved[minHeap[0][1]] != 0:
                    solved[minHeap[0][1]] -= 1
                    heappop(minHeap)
                print(minHeap[0][1])
        # [4] 문제 추가
        elif command[0] == "add":
            p, l = int(command[1]), int(command[2])
            heappush(minHeap,(l,p))
            heappush(maxHeap,(-l,-p))
        # [5] 문제 제거
        elif command[0] == "solved":
            solved[int(command[1])] += 1

# input
N = int(stdin.readline())
PL = [list(map(int,stdin.readline().split())) for _ in range(N)]
M = int(stdin.readline())
commands = [stdin.readline().strip() for _ in range(M)]

# result
solution(N, PL, M, commands)