백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-7662 이중 우선순위 큐 편 (python)

문제 살펴보기!!

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

반응형

---

솔루션 살펴보기!!

import sys
import heapq
from collections import defaultdict

def input():
    return sys.stdin.readline().rstrip()

def process_test_case():
    max_heap = []  # 최대값을 위한 최대 힙
    min_heap = []  # 최소값을 위한 최소 힙
    element_count = defaultdict(int)  # 각 숫자의 삽입 횟수를 기록
    total_elements = 0  # 현재 유효한 원소의 개수

    for _ in range(int(input())):
        operation, number = input().split()

        if operation == 'I':  # 숫자 삽입
            number = int(number)
            heapq.heappush(max_heap, -number)  # 최대값 힙 (부호 변경하여 최대 힙으로 사용)
            heapq.heappush(min_heap, number)  # 최소값 힙
            element_count[number] += 1  # 삽입된 숫자의 개수 증가
            total_elements += 1  # 총 원소 개수 증가

        elif total_elements > 0:  # 삭제 연산 (총 원소가 있을 때만)
            if number == '1':  # 최대값 삭제
                # 유효한 최대값을 찾을 때까지 반복
                while max_heap:
                    max_val = -heapq.heappop(max_heap)
                    if element_count[max_val] > 0:
                        element_count[max_val] -= 1  # 해당 값 개수 감소
                        total_elements -= 1  # 유효한 원소 개수 감소
                        break
            else:  # 최소값 삭제
                # 유효한 최소값을 찾을 때까지 반복
                while min_heap:
                    min_val = heapq.heappop(min_heap)
                    if element_count[min_val] > 0:
                        element_count[min_val] -= 1  # 해당 값 개수 감소
                        total_elements -= 1  # 유효한 원소 개수 감소
                        break

    # 남아있는 유효한 원소가 있을 경우 최대값과 최소값 출력
    if total_elements > 0:
        # 유효한 최대값 찾기
        while max_heap:
            max_val = -heapq.heappop(max_heap)
            if element_count[max_val] > 0:
                break
        # 유효한 최소값 찾기
        while min_heap:
            min_val = heapq.heappop(min_heap)
            if element_count[min_val] > 0:
                break
        print(max_val, min_val)  # 최대값과 최소값 출력
    else:
        print('EMPTY')  # 남아있는 원소가 없을 경우 EMPTY 출력

# 테스트 케이스 개수만큼 처리
for _ in range(int(input())):
    process_test_case()

---

코드 흐름 및 풀이 전략 설명

이 코드는 이중 우선순위 큐 문제를 해결하는 방식으로, 두 개의 우선순위 큐(최대 힙과 최소 힙)를 사용하여 주어진 연산에 맞게 최대값과 최소값을 효율적으로 처리합니다. 각 연산에 대해 삽입과 삭제가 빈번히 발생하므로, 힙 자료구조를 통해 시간 복잡도를 최적화했습니다.

주요 흐름

1. 입력 처리 및 초기화:
   • sys.stdin.readline()으로 입력을 빠르게 처리합니다. 입력으로 주어진 테스트 케이스의 개수와 각 테스트 케이스에서의 연산을 처리합니다.
   • 두 개의 힙을 사용:
     • max_heap: 최대값을 빠르게 찾기 위한 힙 (부호를 반대로 하여 최대 힙처럼 사용)
     • min_heap: 최소값을 빠르게 찾기 위한 힙
   • defaultdict(int)로 원소의 삽입 및 삭제 여부를 관리합니다. 삽입된 숫자가 아직 유효한지(즉, 삭제되지 않은 상태인지)를 추적하기 위함입니다.
2. 삽입 연산 (I):
   • heapq를 사용해 숫자를 두 힙에 동시에 삽입합니다:
     • max_heap: 부호를 반대로 하여 숫자를 넣어 최대 힙처럼 동작시킴.
     • min_heap: 원래 값을 넣어 최소 힙처럼 동작.
   • 삽입된 숫자의 개수를 element_count에서 기록하여, 숫자의 유효성을 관리합니다.
3. 삭제 연산 (D):
   • 최대값 삭제 (D 1): max_heap에서 최대값을 꺼내고, 그 값이 실제로 유효한지 확인합니다. 삭제된 값이 다시 사용되지 않도록 element_count에서 해당 숫자의 카운트를 감소시킵니다.
   • 최소값 삭제 (D -1): min_heap에서 최소값을 꺼내고, 마찬가지로 유효한 값인지 확인한 후 삭제 처리합니다.
   • 힙에 남아 있는 값이 삭제된 값일 수 있기 때문에, 실제로 유효한 값이 나올 때까지 반복해서 꺼내는 방식을 사용합니다.
4. 결과 출력:
   • 모든 연산이 끝난 후, 남아 있는 숫자들 중에서 유효한 최대값과 최소값을 각각 찾아서 출력합니다.
   • 만약 유효한 숫자가 없다면, "EMPTY"를 출력합니다.

---

각 주요 부분에 대한 설명

입력 처리 및 자료구조 초기화

max_heap = []
min_heap = []
element_count = defaultdict(int)
total_elements = 0

 

• max_heap과 min_heap은 각각 최대값과 최소값을 빠르게 찾기 위해 사용됩니다.
• element_count는 숫자의 삽입과 삭제 여부를 추적하여, 힙에서 삭제된 숫자가 힙에 남아있을 수 있는 상황을 처리합니다.

삽입 연산 (Insert operation)

heapq.heappush(max_heap, -number)
heapq.heappush(min_heap, number)
element_count[number] += 1
total_elements += 1

 

 

• 삽입 시, 숫자는 min_heap에 그대로, max_heap에는 부호를 반대로 해서 삽입합니다. 이 방식으로 최대값을 max_heap에서 쉽게 찾을 수 있습니다.
• element_count[number]는 삽입된 숫자의 개수를 증가시킵니다.

삭제 연산 (Delete operation)

if number == '1':  # 최대값 삭제
    while max_heap:
        max_val = -heapq.heappop(max_heap)
        if element_count[max_val] > 0:
            element_count[max_val] -= 1
            total_elements -= 1
            break

 

 

• max_heap에서 최대값을 뽑아내고, 그 값이 유효한지 확인합니다. 유효하지 않다면 계속해서 값을 꺼내 유효한 값이 나올 때까지 반복합니다.
• 유효한 값을 찾으면, 그 숫자의 개수를 element_count에서 감소시키고, 총 원소 개수도 감소시킵니다.

최종 결과 출력

if total_elements > 0:
    while max_heap:
        max_val = -heapq.heappop(max_heap)
        if element_count[max_val] > 0:
            break
    while min_heap:
        min_val = heapq.heappop(min_heap)
        if element_count[min_val] > 0:
            break
    print(max_val, min_val)
else:
    print('EMPTY')

 

• 모든 연산이 끝난 후, 남아있는 유효한 최대값과 최소값을 각각 찾아 출력합니다. 힙에서 유효하지 않은 값들이 남아있을 수 있기 때문에, 유효한 값이 나올 때까지 힙에서 값을 꺼냅니다.

---

코딩 인터뷰 시 답변할 수 있는 주요 개념

1. 이중 우선순위 큐 (Dual Priority Queue):
   • 이중 우선순위 큐는 최대값과 최소값을 모두 효율적으로 처리할 수 있어야 합니다. 이 문제에서는 heapq 모듈을 사용해 두 개의 힙을 구성하고, 하나는 최대값을, 다른 하나는 최소값을 관리하는 방식으로 구현했습니다.
2. Heap 자료구조:
   • Python에서 heapq는 최소 힙을 제공하는데, 이를 활용해 효율적인 삽입 및 삭제 연산을 구현할 수 있습니다. 최대 힙이 필요할 때는 값을 -1 곱해서 힙에 넣는 방법을 사용해 최대 힙처럼 동작하게 할 수 있습니다.
   • 힙을 사용하면 삽입 및 삭제 연산의 시간 복잡도는 O(log⁡N)O(\log N)O(logN)입니다.
3. Lazy Deletion (지연 삭제):
   • 삭제 연산에서 실제로 값이 삭제되었는지 확인하기 위해 힙에 있는 값이 유효한지 확인하는 방식입니다. 값이 힙에 남아있지만 실제로는 삭제된 경우를 처리하기 위해 element_count를 사용해 유효성 여부를 추적합니다.
   • 지연 삭제를 통해 힙에서 유효하지 않은 값을 제거하면서도 성능을 크게 저하시키지 않습니다.
4. defaultdict를 사용한 값 추적:
   • defaultdict(int)를 사용해 삽입된 숫자의 카운트를 관리하며, 이를 통해 각 숫자가 몇 번 삽입되었고 몇 번 삭제되었는지 쉽게 추적할 수 있습니다.
   • 이 방식은 숫자의 유효성을 확인하는 데 중요한 역할을 하며, 이를 통해 힙에서 삭제된 값을 효율적으로 처리할 수 있습니다.
5. 입출력 최적화:
   • sys.stdin.readline()을 사용해 입력을 빠르게 처리하고, 큰 입력을 효과적으로 처리할 수 있도록 성능을 최적화했습니다.