[고득점 kit] 프로그래머스 코딩테스트 연습 - [힙] - #3. 이중우선순위 큐

(문제 설명)

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

명령어수신 탑(높이)

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

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

제한사항

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

입출력 예operationsreturn

["I 16","D 1"]	[0,0]
["I 7","I 5","I -5","D -1"]	[7,5]

입출력 예 설명

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

 

---

( 문제 해설 )

1. 우선위큐 heap은 최소 힙만 지원

2. 두 개의 힙을 만들어서 푸는 방법이 있지만 나는 라이브러리를 적극 이용하겠다.

## 중요 함수 ##

3. heapify는 리스트를 힙화 시켜준다

4. heap.nlargest(원하늘 길이만큼, 해당 힙을)[m: n]  # [m:n]으로 인덱싱

############

 

이걸 안 상태로 조건에 맞게 구현하려고 하면 쉽게 구현할 수 있다.

 

---

[ 코드 ]

 

# 3. 이중우선순위큐
import heapq


def solution(operations):
    oper = []
    Maximum, Minimum = 0, 0
    for i in operations:
        cmd, n = i.split(" ")
        # print(cmd, n)
        if cmd == "I":
            heapq.heappush(oper, int(n))
        # 최대값 삭제
        elif cmd == "D" and n == "1":
            if not oper:
                continue
            oper = heapq.nlargest(len(oper), oper)[1:]
            # print(oper)
            heapq.heapify(oper)
        # 최소값 삭제
        else:
            if not oper:
                continue
            heapq.heappop(oper)

    if oper:
        Maximum = heapq.nlargest(len(oper), oper)[0]
    if oper:
        Minimum = heapq.heappop(oper)
    # print((Maximum), (Minimum))
    answer = [int(Maximum), int(Minimum)]
    return answer


op = ["I 7","I 5","I -5","D -1"]
op1 = ["I 16","D 1"]
op2 = ["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]
op3 = ["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]
sol = solution(op3)
print(sol)

 

 

---

후기

 

두개의 힙을 만들어서 힙은 최소 힙만 지원하므로 하나의 힙에는

-1 곱해서 최대 힙처럼 하나를 만들어서 문제를 푸는 방식도 있습니다.

하지만 저는 함수를 이용하면서 문제 푸는데 먼저 성고 했고 무엇보다

두 개의 힙으로 푸는 방법은 문제에는 주지 않는 히든 케이스를 풀지 못하기에

그냥 올리지는 않았습니다.

저도 위의 코드를 문제를 풀고 다른 사람들의 문제를 참고할 때 대부분 그렇게 풀고 설명도 잘했기에

여기에는 따로 적지는 않습니다