Python - [백준 21939] 문제 추천 시스템 Version 1

참고 포스트:

2025.02.24 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 힙(Heap)으로 우선순위 큐 구현하기 (feat. Lazy Deletion)

[자료구조 & 알고리즘] 힙(Heap)으로 우선순위 큐 구현하기 (feat. Lazy Deletion)

 

2025.02.24 - [Computer Science/알고리즘 문제] - Python - [백준 7662] 이중 우선순위 큐 (feat. 힙, 우선순위큐, Lazy Deletion)

Python - [백준 7662] 이중 우선순위 큐 (feat. 힙, 우선순위큐, Lazy Deletion)

---

 

---

BOJ 21939: 문제 추천 시스템(https://www.acmicpc.net/problem/21939)

 

입력 조건

• 1. N: 초기에 주어지는 문제의 개수 (1 ≤ N ≤ 100,000)
  2. N개의 줄에 걸쳐 P L이 주어짐
     • P: 문제 번호 (1 ≤ P ≤ 100,000)
     • L: 문제의 난이도 (1 ≤ L ≤ 100)
  3. M: 수행할 명령의 개수 (1 ≤ M ≤ 100,000)
  4. M개의 줄에 걸쳐 다음과 같은 명령이 주어짐
     • recommend 1: 현재 남아있는 문제 중 가장 어려운 문제 번호를 출력합니다. (난이도가 같다면 번호가 가장 큰 문제 출력)
     • recommend -1: 현재 남아있는 문제 중 가장 쉬운 문제 번호를 출력합니다. (난이도가 같다면 번호가 가장 작은 문제 출력)
     • add P L: 난이도 L을 가진 문제 번호 P를 추가합니다.
     • solved P: 문제 번호 P를 제거합니다.

출력 조건

• recommend 연산에서 가장 어려운(1), 가장 쉬운(-1) 문제의 번호 P를 출력해야 합니다.

제한 사항

• 1 <= P <= 100000
• 1 <= L <= 100
• 1 <= N, M <= 100000

---

✅ Checkpoint

 

우선순위 큐와 Lazy Deletion을 활용한 대표문제인 이중순위 큐(https://rnasterofmysea.tistory.com/149)를 응용하는 문제였습니다 - 동일하게 최대값을 처리할 수 있는 max_heap 과 최소값을 처리할 수 있는 min_heap, 2개의 힙과 Lazy Deletion을 위한 valid 딕셔너리가 사용되었습니다.

 

차이점은 문제를 추가할 수 있는 problem_set 이라는 집합 추가적으로 사용되었다는 점입니다.

 

recommend 요구사항을 살펴보면 문제 번호가 아닌 난이도의 최대값과 최소값입니다.

그렇기 때문에 max_heap과 min_heap에 값을 저장할 때 기준이 되는점은 문제번호가 아닌 난이도가 됩니다.

    P, L = map(int, input().strip().split())
    heapq.heappush(min_heap, (L, P))  # 최소 힙: 난이도 기준 정렬
    heapq.heappush(max_heap, (-L, -P))  # 최대 힙: 난이도 내림차순 정렬

 

 

valid 딕셔너리에 문제 번호를 KEY, 난이도를 VALUE 로 사용합니다.

만약 valid 딕셔너리의 KEY가 난이도라면, 같은 난이도에 문제번호가 다른 값들을 처리하지 못하게됩니다.

그렇기 때문에 valid 딕셔너리에 문제 번호를 KEY, 난이도를 VALUE는 고정해놓고 처리해야합니다.

valid = {}  # 문제 유효성 저장 (P -> L)
.
.
.

valid[P] = L  # 문제 유효성 저장

 

이렇게만 처리해도 전체 알고리즘을 구현하는데 문제가 없습니다.

하지만 오답입니다.( 하단엔 오류 코드)

"""
python_boj_21939_문제 추천 시스템 Version 1
https://www.acmicpc.net/problem/21939
"""
import sys
import heapq

input = sys.stdin.readline

max_heap = []  # 최대 힙 (난이도 높은 문제 찾기)
min_heap = []  # 최소 힙 (난이도 낮은 문제 찾기)
valid = {}  # 문제 유효성 저장

N = int(input().strip())
for _ in range(N):
    P, L = map(int, input().strip().split())
    heapq.heappush(min_heap, (L, P))  # 최소 힙: 난이도 기준 정렬
    heapq.heappush(max_heap, (-L, -P))  # 최대 힙: 난이도 내림차순 정렬
    valid[(L, P)] = True  # 문제 유효성 저장

M = int(input().strip())
for _ in range(M):
    prompt = input().strip().split()

    if prompt[0] == "recommend":
        """
        가장 어려운 문제 또는 쉬운 문제 출력
        """
        if prompt[1] == "1":
            # 가장 어려운 문제 찾기 (유효한 문제만 유지)
            while max_heap and not valid.get((-max_heap[0][0], -max_heap[0][1]), False):
                heapq.heappop(max_heap)  # 유효하지 않은 문제 제거
            print(-max_heap[0][1])  # P 출력
        else:
            # 가장 쉬운 문제 찾기 (유효한 문제만 유지)
            while min_heap and not valid.get((min_heap[0][0], min_heap[0][1]), False):
                heapq.heappop(min_heap)  # 유효하지 않은 문제 제거
            print(min_heap[0][1])  # P 출력

    elif prompt[0] == "add":
        """
        새로운 문제 추가
        """
        P, L = int(prompt[1]), int(prompt[2])
        heapq.heappush(min_heap, (L, P))
        heapq.heappush(max_heap, (-L, -P))
        valid[(L, P)] = True  # 문제 추가

    elif prompt[0] == "solved":
        """
        특정 문제를 푼 것으로 처리
        """
        P = int(prompt[1])
        for key in valid.keys():
            if key[1] == P:
                valid[key] = False  # 해당 문제 무효화
                break

 

제출을 해보면 시간 초과가 발생합니다.

 

이 부분을 해결하지 못해 답을 확인하게 되었는데,

이유는 즉슨, "solved" 명령어를 처리할 때 O(N)의 시간복잡도가 발생하기 때문입니다.

 

    elif prompt[0] == "solved":
        """
        특정 문제를 푼 것으로 처리
        """
        P = int(prompt[1])
        for key in valid.keys():
            if key[1] == P:
                valid[key] = False  # 해당 문제 무효화
                break

 

 

이를 해결하기 위해 valid 딕셔너리와 함께 problem_set을 추가로 사용해야 합니다. problem_set은 힙과 valid 사이에서 문제를 저장하여, solved 연산을 O(1)로 빠르게 처리할 수 있도록 합니다. (문제 번호를 O(1)로 검색할 수 있도록 valid을 P -> L 형식으로 유지하고, problem_set을 도입합니다.)

#문제 추가 시
N = int(input().strip())
for _ in range(N):
    P, L = map(int, input().strip().split())
    heapq.heappush(min_heap, (L, P))  # 최소 힙: 난이도 기준 정렬
    heapq.heappush(max_heap, (-L, -P))  # 최대 힙: 난이도 내림차순 정렬
    valid[P] = L  # 문제 유효성 저장
    problem_set.add((L, P))  # 문제 추가
  

# (..중간 생략..) 
 
elif prompt[0] == "solved":
        """
        특정 문제를 푼 것으로 처리
        """
        P = int(prompt[1])
        if P in valid:
            L = valid[P]  # 해당 문제의 난이도를 가져옴
            del valid[P]  # 문제 삭제
            problem_set.remove((L, P))  # 문제를 유효 목록에서 제거

 

💡 개선된 방식의 원리

1. valid 딕셔너리를 활용하여 문제 번호(P)를 키로 조회
   • if P in valid:를 사용하면 O(1)로 빠르게 확인 가능.
   • valid[P]에서 해당 문제의 난이도 L을 가져옴.
2. valid에서 P를 삭제(O(1))
   • 더 이상 유효하지 않은 문제이므로 del valid[P] 수행.
3. problem_set에서 (L, P) 삭제(O(1))
   • heapq에서 직접 삭제하면 O(N) 시간이 걸리므로, 대신 삭제된 문제를 problem_set에서 제거하여 힙에서 Lazy Deletion이 가능하도록 설정.

 

요약

1. 최대 힙(max_heap): 난이도가 높은 문제를 쉽게 찾기 위해 사용
   • 저장 방식: (-L, -P) (난이도 L을 내림차순 정렬, 동일한 난이도에서는 P를 내림차순 정렬)
2. 최소 힙(min_heap): 난이도가 낮은 문제를 쉽게 찾기 위해 사용
   • 저장 방식: (L, P) (난이도 L을 오름차순 정렬, 동일한 난이도에서는 P를 오름차순 정렬)
3. 해시 테이블(valid): 문제의 유효성을 저장 ({P: L} 형태)
4. 집합(problem_set): 유효한 (L, P) 값을 빠르게 관리

 

---

Python 코드 (최적 풀이)

import sys
import heapq

input = sys.stdin.readline

max_heap = []  # 최대 힙 (난이도 높은 문제 찾기)
min_heap = []  # 최소 힙 (난이도 낮은 문제 찾기)
valid = {}  # 문제 유효성 저장 (P -> L 저장)
problem_set = set()  # (L, P) 형태 저장 (유효성 확인용)

N = int(input().strip())
for _ in range(N):
    P, L = map(int, input().strip().split())
    heapq.heappush(min_heap, (L, P))  # 최소 힙: 난이도 기준 정렬
    heapq.heappush(max_heap, (-L, -P))  # 최대 힙: 난이도 내림차순 정렬
    valid[P] = L  # 문제 유효성 저장
    problem_set.add((L, P))  # 문제 추가

M = int(input().strip())
for _ in range(M):
    prompt = input().strip().split()

    if prompt[0] == "recommend":
        if prompt[1] == "1":
            while max_heap and (-max_heap[0][0], -max_heap[0][1]) not in problem_set:
                heapq.heappop(max_heap)  # 유효하지 않은 문제 제거
            print(-max_heap[0][1])  # P 출력
        else:
            while min_heap and (min_heap[0][0], min_heap[0][1]) not in problem_set:
                heapq.heappop(min_heap)  # 유효하지 않은 문제 제거
            print(min_heap[0][1])  # P 출력

    elif prompt[0] == "add":
        P, L = int(prompt[1]), int(prompt[2])
        heapq.heappush(min_heap, (L, P))
        heapq.heappush(max_heap, (-L, -P))
        valid[P] = L  # 문제 추가
        problem_set.add((L, P))  # 문제 추가

    elif prompt[0] == "solved":
        P = int(prompt[1])
        if P in valid:
            L = valid[P]  # 해당 문제의 난이도를 가져옴
            del valid[P]  # 문제 삭제
            problem_set.remove((L, P))  # 문제를 유효 목록에서 제거

 

1️⃣ 입력 및 데이터 구조 초기화

import sys
import heapq

input = sys.stdin.readline

max_heap = []  # 최대 힙 (난이도 높은 문제 찾기)
min_heap = []  # 최소 힙 (난이도 낮은 문제 찾기)
valid = {}  # 문제 유효성 저장 (P -> L)
problem_set = set()  # (L, P) 형태 저장 (유효성 확인용)

• max_heap: 가장 어려운 문제를 찾을 때 사용합니다. (-L, -P) 형태로 저장하여 Python의 기본 힙(min-heap)을 최대 힙처럼 활용합니다.
• min_heap: 가장 쉬운 문제를 찾을 때 사용합니다. (L, P) 형태로 저장하여 기본적으로 난이도 오름차순으로 정렬됩니다.
• valid: 문제 P의 난이도 L을 저장하는 딕셔너리입니다. 특정 문제가 존재하는지 확인하는 데 사용됩니다.
• problem_set: 현재 존재하는 문제를 (L, P) 형태로 저장하여, 힙에서 무효한 데이터를 제거할 때 사용됩니다.

---

2️⃣ 초기 데이터 입력

N = int(input().strip())
for _ in range(N):
    P, L = map(int, input().strip().split())
    heapq.heappush(min_heap, (L, P))  # 최소 힙: 난이도 기준 정렬
    heapq.heappush(max_heap, (-L, -P))  # 최대 힙: 난이도 내림차순 정렬
    valid[P] = L  # 문제 유효성 저장
    problem_set.add((L, P))  # 문제 추가

• heapq.heappush(min_heap, (L, P))
  → 난이도 L이 낮은 문제를 빠르게 찾기 위해 최소 힙에 저장합니다.
• heapq.heappush(max_heap, (-L, -P))
  → 난이도가 높은 문제를 찾을 때 활용하기 위해 최대 힙을 구현합니다.
• valid[P] = L
  → 문제 P의 난이도 L을 기록합니다.
• problem_set.add((L, P))
  → 현재 존재하는 문제를 관리하는 Set에 추가합니다.

---

3️⃣ 명령어 처리

M = int(input().strip())
for _ in range(M):
    prompt = input().strip().split()

• M: 명령어의 개수입니다.
• prompt = input().strip().split(): 명령어를 공백을 기준으로 나누어 리스트로 저장합니다.

---

4️⃣ 문제 추천 (recommend)

if prompt[0] == "recommend":
    if prompt[1] == "1":
        # 가장 어려운 문제 찾기 (유효한 문제만 유지)
        while max_heap and (-max_heap[0][0], -max_heap[0][1]) not in problem_set:
            heapq.heappop(max_heap)  # 유효하지 않은 문제 제거
        print(-max_heap[0][1])  # P 출력
    else:
        # 가장 쉬운 문제 찾기 (유효한 문제만 유지)
        while min_heap and (min_heap[0][0], min_heap[0][1]) not in problem_set:
            heapq.heappop(min_heap)  # 유효하지 않은 문제 제거
        print(min_heap[0][1])  # P 출력

✅ recommend 1
가장 어려운 문제를 찾습니다.

• max_heap에서 가장 큰 값을 꺼내지만, problem_set에 존재하는지 확인한 후 유효한 문제만 출력합니다.

✅ recommend -1
가장 쉬운 문제를 찾습니다.

• min_heap에서 가장 작은 값을 꺼내되, problem_set에 있는 문제만 출력합니다.

---

5️⃣ 문제 추가 (add)

elif prompt[0] == "add":
    P, L = int(prompt[1]), int(prompt[2])
    heapq.heappush(min_heap, (L, P))
    heapq.heappush(max_heap, (-L, -P))
    valid[P] = L  # 문제 추가
    problem_set.add((L, P))  # 문제 추가

• 새로운 문제 (P, L)을 min_heap과 max_heap에 삽입합니다.
• valid[P] = L을 통해 문제 정보를 저장합니다.
• problem_set.add((L, P))으로 문제의 존재 여부를 체크합니다.

---

6️⃣ 문제 삭제 (solved)

elif prompt[0] == "solved":
    P = int(prompt[1])
    if P in valid:
        L = valid[P]  # 해당 문제의 난이도를 가져옴
        del valid[P]  # 문제 삭제
        problem_set.remove((L, P))  # 문제를 유효 목록에서 제거

• 문제 P가 존재하면 valid 딕셔너리에서 삭제합니다.
• problem_set에서도 제거하여 이후 recommend 명령에서 유효하지 않은 문제를 제거할 수 있도록 합니다.
• heap에서 바로 삭제하지 않는 이유
  Python의 heapq는 특정 요소를 중간에서 제거하는 기능이 없습니다. 따라서 problem_set에서 제거만 해두고, 이후 recommend를 호출할 때 힙에서 무효 데이터를 걸러내는 방식으로 처리합니다.

 

---

⏳ 오답 VS 정답 시간 복잡도 비교 표

연산 종류	오답 코드 시간 복잡도	정답 코드 시간 복잡도	설명
add	O(log N)	O(log N)	힙에 삽입
solved	O(N)	O(1)	문제 무효화 방식 차이
recommend	O(log N)	O(log N)	힙에서 유효 문제 찾기
전체 시간 복잡도	O(M log N + M N)	O(M log N)	solved 연산 최적화

• 오답 코드: solved 연산이 많아질수록 O(MN)이 되어 비효율적.
• 정답 코드: solved 연산이 O(1)로 최적화되어 O(M log N) 유지.

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.