프로그래머스 Lv.3: 이중우선순위큐 - Python 풀이

문제 설명

프로그래머스

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어	해석
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

입출력 예

operations	return
["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]	[0,0]
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]	[333, -45]

입출력 예 설명

입출력 예 #1

• 16과 -5643을 삽입합니다.
• 최솟값을 삭제합니다. -5643이 삭제되고 16이 남아있습니다.
• 최댓값을 삭제합니다. 16이 삭제되고 이중 우선순위 큐는 비어있습니다.
• 우선순위 큐가 비어있으므로 최댓값 삭제 연산이 무시됩니다.
• 123을 삽입합니다.
• 최솟값을 삭제합니다. 123이 삭제되고 이중 우선순위 큐는 비어있습니다.

따라서 [0, 0]을 반환합니다.

입출력 예 #2

• 45와 653을 삽입후 최댓값(653)을 삭제합니다. -45가 남아있습니다.
• 642, 45, 97을 삽입 후 최댓값(97), 최솟값(-642)을 삭제합니다. -45와 45가 남아있습니다.
• 333을 삽입합니다.

이중 우선순위 큐에 -45, 45, 333이 남아있으므로, [333, -45]를 반환합니다.

문제 요약) 명령에 따라 배열에 값을 추가, 최댓값 pop, 최솟값 pop의 연산을 수행한 후, 배열에 값이 존재하지 않으면 [0, 0]을, 값이 존재하면 [최댓값, 최솟값]을 반환해라.

풀이 과정

파이썬의 heapq를 사용하여 최소힙 자료구조를 사용했습니다.

다만, 최댓값을 pop 해야 하는 경우도 있기 때문에 최대힙도 만들어야 합니다.

heapq는 기본적으로 최소힙을 구성하기 때문에, heapq를 사용해서 최대힙 로직(= pop 했을 때 최댓값이 나오게)을 구현하려면 - 부호를 붙이면 됩니다. 예를 들어 [12, 32] 처럼 최소힙이 구성될 때 마이너스를 붙여 -32와 -12로 바꾼다면 최솟값이 루트에 오도록 [-32, -12] 와 같이 구성될 겁니다. 이때 heappop을 하면 -32가 출력될 것이고, 이 값에 다시 -를 붙인다면 처음 [12, 32]에서의 최댓값인 32를 얻을 수 있게 됩니다.

최종적으로 최소힙, 최대힙 2개를 따로 두어 사용했고, 값이 추가될 때 2개 모두에 추가, 삭제될 때 2개 모두에서 삭제하는 방식으로 구현했습니다. 2개의 싱크를 맞춰주는 게 핵심!

정답 코드

import heapq as hq

def solution(operations):
    answer = []
    min_heap = []
    max_heap = []
    
    # 명령의 개수만큼 반복
    for oper in operations:
        command, value = oper.split()
        value = int(value)
        
        # I 명령이면
        if command == "I":
            # 값을 삽입
            hq.heappush(min_heap, value)
            # 최대힙에는 - 부호를 붙여서 push
            hq.heappush(max_heap, -value)
        # D 1 명령이고 최대힙이 비어 있지 않으면
        elif command == "D" and value == 1 and max_heap:
            # 최대힙에서 최댓값 제거
            hq.heappop(max_heap)
            # 최소힙도 최댓값 제거된 버전으로 업데이트
            # 둘은 저장된 값의 부호가 다르기 때문에 -1 곱한 것으로 업데이트
            min_heap = list(map(lambda x: x * -1, max_heap))
            # 최소힙 로직을 유지하도록 heapify 함수 사용
            hq.heapify(min_heap)
        # D -1 명령이고 최소힙이 비어 있지 않으면
        elif command == "D" and value == -1 and min_heap:
            # 최소힙에서 최솟값 제거
            hq.heappop(min_heap)
            # 최대힙도 최솟값 제거된 버전으로 업데이트
            # 둘은 저장된 값의 부호가 다르기 때문에 -1 곱한 것으로 업데이트
            max_heap = list(map(lambda x: x * -1, min_heap))
            # 최대힙 로직을 유지하도록 heapify 함수 사용
            hq.heapify(max_heap)
    # 배열이 비어 있지 않으면
    if min_heap and max_heap:
        # [최댓값, 최솟값]을 출력해야 해서 해당하는 값을 순서대로 append
        answer.append(-hq.heappop(max_heap))
        answer.append(hq.heappop(min_heap))
    # 배열이 비어 있으면
    else:
        # [0, 0]을 출력해야 해서 0을 2번 append
        answer.append(0)
        answer.append(0)
        
    return answer

 

이상입니다.