알고리즘 풀이: [프로그래머스] 이중우선순위큐

https://programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐

문제 설명

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

 

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 취솟값을 삭제합니다.

 

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

 

제한 사항

operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.

 

operations의 원소는 큐가 수행할 연산을 나타냅니다.

 

원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.

 

빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

 

입출력 예

operations	return
["I 16", "D 1"]	[0, 0]
["I 7", "I 5", "I -5", "D -1"]	[7, 5]
["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]
["I 1", "I 2", "I 3", "I 4", "I 5", "I 6", "I 7", "I 8", "I 9", "I 10", "D 1", "D -1", "D 1", "D -1", "I 1", "I 2", "I 3", "I 4", "I 5", "I 6", "I 7", "I 8", "I 9", "I 10", "D 1", "D -1", "D 1", "D -1"]	[8, 3]
["I 4", "I 3", "I 2", "I 1", "D 1", "D 1", "D -1", "D -1", "I 5", "I 6"]	[6, 5]
["I 2", "I 2", "I 3", "D -1", "D 1", "D 1"]	[0, 0]

 

입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.

7,5,-5를 삽입 후 최솟값을 삭제합니다. 최댓값 7, 최솟값 5를 반환합니다.

---

문제 풀이

operations의 연산을 순차적으로 처리합니다.

 

최소 힙 자료 구조 한 개로 충분합니다.

 

초기화 및 연산 설명

"I 숫자" 연산은 힙에 숫자를 push 하고, 최솟값을 구하는 "D -1" 연산은 힙에서 숫자를 pop 합니다. "D 1" 연산은 최댓값을 구하는 연산으로 현재 최소 힙 하나만을 사용하였으므로 최댓값을 찾고 리스트 연산으로 최댓값을 제거합니다.

 

 

단계 1: I 연산 처리

I 연산으로 4, 3, 2, 1 숫자 삽입

 

I 연산으로 숫자 4, 3, 2, 1을 차례대로 힙에 push 합니다. 최소 힙이기 때문에 부모는 자식보다 무조건 작은 숫자를 가지며, 루트에는 최솟값이 저장되어 있습니다.

 

 

단계 2: D 연산 처리

 

D 연산으로 최대값 2개와 최소값 2개 제거

D 1 연산은 최댓값을 제거하는 연산입니다. 최소 힙에서 최댓값을 구할 수 있는 방법은 없습니다. 다만 파이썬에서 힙은 리스트로 구현합니다. 따라서 최댓값을 찾고 리스트 연산으로 제거합니다.

 

D -1 연산은 최솟값을 제거하는 연산입니다. 최소 힙에서 pop 연산을 하면 최솟값을 제거할 수 있습니다.

 

 

단계 3: I 연산 처리

 

I 연산으로 숫자 5, 6 추가

마지막 I 연산으로 숫자 5와 6을 힙에 push 합니다.

 

 

최종 결과

 

최종 단계

현재 힙에 남아있는 숫자를 바탕으로 최댓값과 최솟값을 반환합니다.

 

소스 코드

메인 솔루션 함수

import heapq


def solution(operations):
    # 숫자를 관리할 최소 힙 (min heap)
    heap = list()

    for operation in operations:
        # heap push
        if operation[0] == 'I':
            num = int(operation[2:])
            heapq.heappush(heap, num)
        # heap pop
        elif operation == 'D -1':
            if heap:
                heapq.heappop(heap)
        # 최대값을 찾아서 리스트에서 제거
        elif operation == 'D 1':
            if heap:
                heap.remove(max(heap))

    return [max(heap), heap[0]] if heap else [0, 0]


if __name__ == '__main__':
    assert solution(["I 16", "D 1"]) == [0, 0]
    assert solution(["I 7", "I 5", "I -5", "D -1"]) == [7, 5]
    assert solution(["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]) == [0, 0]
    assert solution(["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]) == [333, -45]
    assert solution(["I 1", "I 2", "I 3", "I 4", "I 5",
                     "I 6", "I 7", "I 8", "I 9", "I 10",
                     "D 1", "D -1", "D 1", "D -1", "I 1",
                     "I 2", "I 3", "I 4", "I 5", "I 6",
                     "I 7", "I 8", "I 9", "I 10", "D 1",
                     "D -1", "D 1", "D -1"]) == [8, 3]
    assert solution(["I 4", "I 3", "I 2", "I 1", "D 1", "D 1", "D -1", "D -1", "I 5", "I 6"]) == [6, 5]
    assert solution(["I 2", "I 2", "I 3", "D -1", "D 1", "D 1"]) == [0, 0]

프로그래머스

github 주소: https://github.com/dhsong95/-PRACTICE-Programmers-Algorithm/blob/master/level%203/%EC%9D%B4%EC%A4%91%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84%ED%81%90.py

dhsong95/-PRACTICE-Programmers-Algorithm