[백준] 7662 이중 우선순위 큐

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

값을 추가하고 최솟값과 최댓값을 삭제하는 연산이 존재하여 최소힙을 이용해 데이터를 다루도록 접근

 

최소힙과 최대힙 2개를 사용하려 했으나 각자의 리스트에서 어떤 값들이 이미 삭제된건지 판별하기 어려울것 같아서 최소힙 하나로 진행

최소힙에서 최댓값 삭제할때는 내장된 max 함수와 리스트의 remove 함수를 이용해 제거하는 방식으로 접근하였으나 시간초과로 실패

 

최소힙과 최대힙 두개를 사용하는대신 어떤게 삭제 되었는지 판별하는 로직 추가하여 접근

2) 알고리즘

• 최소힙

3) 풀이 코드

사용 언어 - Python

import sys
import heapq
sys.stdin = open('input.txt')


T = int(sys.stdin.readline())                                   # 테스트 케이스 개수

for _ in range(T):
    K = int(sys.stdin.readline())                               # 명령의 개수
    min_heap, max_heap = [], []                                 # 최소힙, 최대힙으로 사용할 리스트
    deleted = [0] * (K+1)                                       # 삭제된 숫자들 목록 리스트 (0-삭제되지 않음, 1-삭제됨)

    for i in range(K):
        command, num = sys.stdin.readline().split()             # 명령어 종류, 숫자
        num = int(num)

        if command == 'I':                                      # 삽입 연산
            heapq.heappush(min_heap, (num, i))                  # 최소힙과 최대힙에 모두 추가
            heapq.heappush(max_heap, (-num, i))                        

        elif command == 'D' and max_heap:                       # 삭제 연산
            if num == -1:                                       # 최소힙 삭제인 경우
                while min_heap and deleted[min_heap[0][1]]:     # 최소힙에 값이 남아있고, 현재 최솟값의 인덱스가 최대힙에서 삭제된 인덱스이면 삭제
                    heapq.heappop(min_heap)
                if min_heap:                                    # 여전히 최소힙이 남아있으면
                    node = heapq.heappop(min_heap)              # 최솟값 삭제
                    deleted[node[1]] = 1                        # 삭제한 최솟값의 인덱스를 삭제 처리

            else:                                               # 최대힙 삭제인 경우
                while max_heap and deleted[max_heap[0][1]]:     # 최대힙에 값이 남아있고, 현재 최댓값의 인덱스가 최소힙에서 삭제된 인덱스이면 삭제
                    heapq.heappop(max_heap)                             
                if max_heap:                                    # 최대힙이 남아있으면
                    node = heapq.heappop(max_heap)              # 최댓값 삭제 및 방금 삭제한 최댓값의 인덱스 삭제 처리
                    deleted[node[1]] = 1

    while min_heap and deleted[min_heap[0][1]]:                 # 최소힙에서 최솟값이 최대힙에서 삭제됬으면 삭제
        heapq.heappop(min_heap)                                
    while max_heap and deleted[max_heap[0][1]]:                 # 최대힙에서 최댓값이 최소힙에서 삭제됬으면 삭제
        heapq.heappop(max_heap)

    if not min_heap:                                            # 출력
        print('EMPTY')
    else:
        print(-heapq.heappop(max_heap)[0], heapq.heappop(min_heap)[0])

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

명령어의 개수가 많고, 삭제 연산시 생기는 시간문제로 시간 초과를 해결하는데 어려움을 겪음

최소힙과 최대힙 두개를 같이 사용하고 싶었으나 두개의 데이터를 항상 같은 상태로 유지시키는 방식을 떠올리기 어려웠음

(1) 참고 사이트

• 블로그
  최소힙과 최대힙의 데이터를 동기화 시켜주는 로직 참고

2) 새롭게 학습한 내용

여러 리스트의 값을 서로 동기화 시킬때 그 값의 인덱스를 이용하여 동기화 시킬 수 있음

---

🔗 문제 링크

- https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다