백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-21939 문제 추천 시스템 Version 1 편 (python)

문제 살펴보기!!

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

---

반응형

솔루션 살펴보기!!

import sys
import heapq

class ProblemManager:
    def __init__(self):
        # Dictionary to store current problems with their levels
        self.num_to_level = {}
        # Max heap: (-level, -num)
        self.max_heap = []
        # Min heap: (level, num)
        self.min_heap = []

    def add_problem(self, num, level):
        """Add a new problem to the manager."""
        self.num_to_level[num] = level
        heapq.heappush(self.max_heap, (-level, -num))
        heapq.heappush(self.min_heap, (level, num))

    def solve_problem(self, num):
        """Mark a problem as solved by removing it from the manager."""
        if num in self.num_to_level:
            del self.num_to_level[num]

    def recommend(self, n):
        """
        Recommend a problem based on the command.
        If n == 1, recommend the hardest problem with the highest number.
        If n == 2, recommend the easiest problem with the lowest number.
        """
        if n == 1:
            # Recommend the hardest problem
            while self.max_heap:
                level, num = self.max_heap[0]
                level = -level
                num = -num
                if num in self.num_to_level and self.num_to_level[num] == level:
                    return num
                else:
                    # Remove invalid entry
                    heapq.heappop(self.max_heap)
        else:
            # Recommend the easiest problem
            while self.min_heap:
                level, num = self.min_heap[0]
                if num in self.num_to_level and self.num_to_level[num] == level:
                    return num
                else:
                    # Remove invalid entry
                    heapq.heappop(self.min_heap)
        return -1  # In case there are no problems

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0

    pm = ProblemManager()

    N = int(data[idx])
    idx += 1

    # Read initial problems
    for _ in range(N):
        num = int(data[idx])
        lev = int(data[idx + 1])
        pm.add_problem(num, lev)
        idx += 2

    M = int(data[idx])
    idx += 1

    output = []

    for _ in range(M):
        command = data[idx]
        idx += 1

        if command == "add":
            num = int(data[idx])
            lev = int(data[idx + 1])
            pm.add_problem(num, lev)
            idx += 2
        elif command == "solved":
            num = int(data[idx])
            pm.solve_problem(num)
            idx += 1
        elif command == "recommend":
            n = int(data[idx])
            recommended_num = pm.recommend(n)
            output.append(str(recommended_num))
            idx += 1

    # Print all recommendations at once for efficiency
    print('\n'.join(output))

if __name__ == "__main__":
    main()

---

코드 흐름 및 풀이 전략

이 코드는 문제 관리 시스템을 구현한 것입니다. 다양한 문제들이 주어지고, 이를 해결하거나 추천하는 작업을 효율적으로 수행할 수 있도록 설계되어 있습니다. 사용자는 문제를 추가하고, 문제를 해결할 수 있으며, 가장 어려운 혹은 가장 쉬운 문제를 추천받을 수 있습니다.

문제 관리 시스템의 요구사항:

1. 문제 추가: 새로운 문제와 난이도를 추가할 수 있어야 합니다.
2. 문제 해결: 해결한 문제를 시스템에서 제거할 수 있어야 합니다.
3. 문제 추천:
   • recommend 1: 가장 어려운 문제 중에서 문제 번호가 가장 큰 문제를 추천합니다.
   • recommend 2: 가장 쉬운 문제 중에서 문제 번호가 가장 작은 문제를 추천합니다.

주요 개념 및 자료구조

1. Heap (힙):

• 최대 힙 (max_heap): 난이도가 높은 문제를 쉽게 찾기 위해 사용됩니다. (-level, -num) 형태로 저장하여 난이도는 내림차순으로, 난이도가 같으면 문제 번호는 큰 순서대로 정렬됩니다.
• 최소 힙 (min_heap): 난이도가 낮은 문제를 쉽게 찾기 위해 사용됩니다. (level, num) 형태로 저장하여 난이도는 오름차순으로, 난이도가 같으면 문제 번호는 작은 순서대로 정렬됩니다.
• Python의 heapq 라이브러리는 기본적으로 최소 힙을 지원하기 때문에, 최대 힙을 구현하려면 값을 음수로 저장하여 반대로 정렬되도록 만들었습니다.

2. 딕셔너리 (num_to_level):

• 각 문제 번호에 대한 난이도를 저장하는 딕셔너리입니다. 이를 통해 문제 해결 및 추천 시 문제의 존재 여부를 빠르게 확인할 수 있습니다.

코드 흐름

1. 초기 문제 입력:
   • 프로그램이 실행되면 먼저 주어진 문제 수(N)를 입력받고, 각 문제와 그에 따른 난이도를 add_problem 함수를 통해 시스템에 추가합니다.
2. 문제 처리:
   • 추가된 문제에 대해 여러 명령어를 처리합니다. 명령어는 add, solved, recommend로 나뉘며, 각각 다른 기능을 수행합니다.
     • add num lev: 문제 번호 num과 난이도 lev를 추가합니다.
     • solved num: 문제 번호 num을 해결(삭제)합니다.
     • recommend n:
       • n == 1: 가장 어려운 문제 중 문제 번호가 큰 문제를 추천합니다.
       • n == 2: 가장 쉬운 문제 중 문제 번호가 작은 문제를 추천합니다.
3. 힙 정리:
   • recommend 함수에서 추천을 수행할 때, 힙에서 유효하지 않은 문제(이미 해결된 문제)를 삭제하며 최상단의 유효한 문제를 찾아 반환합니다. 유효하지 않은 문제는 힙의 최상위에 있을 수 있는데, 이런 문제들을 heapq.heappop()으로 제거하면서 유효한 문제를 찾습니다.
4. 출력 최적화:
   • 추천된 문제는 리스트에 저장되며, 마지막에 한 번에 출력하여 I/O 효율성을 높입니다.

---

주요 개념 정리

1. Heap (힙):

• 최소 힙은 부모 노드가 자식 노드보다 작은 값을 가지는 트리 구조입니다. 파이썬의 heapq는 최소 힙만 지원하지만, 값을 음수로 변환하여 최대 힙으로 활용할 수 있습니다.
• 힙을 이용하면 삽입 및 삭제의 시간 복잡도가 O(log n)이므로, 효율적으로 가장 큰/작은 문제를 관리할 수 있습니다.

2. 딕셔너리 (해시 맵):

• 딕셔너리는 키-값 쌍을 저장하는 자료구조로, 문제 번호를 키로, 난이도를 값으로 저장하여 해결한 문제의 유무를 빠르게 확인할 수 있습니다.
• 딕셔너리의 조회, 삽입, 삭제는 평균적으로 O(1)입니다.

풀이 전략

1. 문제 추가 시:
   • 문제는 max_heap과 min_heap에 모두 저장되며, 문제 번호와 난이도는 num_to_level 딕셔너리에 기록됩니다.
2. 문제 해결 시:
   • 문제 해결은 딕셔너리에서 해당 문제를 삭제합니다. 힙에서는 별도로 문제를 제거하지 않고, 이후에 유효성 검사를 통해 해결된 문제를 무시합니다.
3. 추천 시:
   • recommend 1 (어려운 문제 추천): max_heap의 최상단에 있는 문제부터 유효성을 검사하여 추천합니다.
   • recommend 2 (쉬운 문제 추천): min_heap의 최상단에 있는 문제부터 유효성을 검사하여 추천합니다.

시간 복잡도 분석

• 문제 추가 및 해결: 각 문제는 힙에 삽입 및 삭제되므로 O(log n)의 시간이 소요됩니다.
• 추천 작업: 힙에서 최상단에 있는 문제를 꺼내므로 O(log n) 시간이 걸립니다.