[프로그래머스 스터디 6주차] 힙 이중우선순위큐 Lv.3 - 파이썬(Python)

📑 문제

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의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

 

 

 

 

 

 

 

 

 

✒️ 풀이

 파이썬의 heapq는 최소힙을 기준으로 이뤄진다고 하기에, 최대힙의 경우에는 마이너스를 붙여서 운용했다.

 ex) 1,3,5에 마이너스를 붙여서 최소힙에 넣어주면 최대힙처럼 -5,-3,-1으로 정렬된다.

 

◻️ 오퍼레이션에 맞게 값을 넣거나 뺀다.

◻️ 힙 두 개는 최대/최소값을 빨리 찾기 위해 운용하는 것일 뿐, 값이 들어가고 빠지는건 똑같이 일어나야 한다. 

◻️ 최대값을 빼면 max_heap에서, 최소값을 빼면 min_heap에서 값을 꺼낸 후에 남은 다른 힙에서도 해당 값을 똑같이 빼준다. 

◻️ 모든 연산이 끝나면 max_heap에서 하나, min_heap에서 하나를 꺼내어 최대/최소값으로 리턴해준다.

 

 

 

 

 

 

🙋‍♀️ 의견

 최대힙/최소힙을 둘 다 두고 쓰는게 좋은 코드인지는 모르겠지만.....통과했으니 올려본다.

 

 

 

 

 

 

 

💻 소스코드: 파이썬(Python)

import heapq

def solution(operations):
    min_heap = []
    max_heap = []
    for op in operations:
        o, n = op.split()

        if o=="I":
            # heappush: O(logN)
            heapq.heappush(min_heap, int(n))
            heapq.heappush(max_heap, -int(n))

        if len(min_heap)!=0:
            # heappop: O(logN)
            # heapify: O(N)
            if o=="D" and n=="1":
                max = -heapq.heappop(max_heap)
                min_heap.remove(max)
                heapq.heapify(min_heap)
            elif o=="D" and n=="-1":
                min = heapq.heappop(min_heap)
                max_heap.remove(-min)
                heapq.heapify(max_heap)

    if len(max_heap)==0:
        return [0,0]
    return [-heapq.heappop(max_heap), heapq.heappop(min_heap)]



#예시
operations = ["I 7","I 5","I -5","D -1"]

#출력
print(solution(operations))

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨