[Python] 프로그래머스 Lv3_이중우선순위큐

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

프로그래머스

 

 

• operations: 이중 우선순위 큐가 할 연산
• 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return

제한사항

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

 

"""
입출력 예시)

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

 

# operations = ["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"] -> [0,0]

# "I 16": 16 삽입
# "I -5643": -5643 삽입
# "D -1": 최솟값 삭제 -> -5643이 삭제되고 16이 남아있음
# "D 1": 최댓값 삭제 -> 16이 삭제되고 이중 우선순위 큐는 비어있음
# "D 1": 우선순위 큐가 비어있으므로 최댓값 삭제 연산 무시
# "I 123": 123 삽입
# "D -1": 최솟값 삭제 -> 123이 삭제되고 이중 우선순위 큐는 비어있음

# => [0, 0]

# operations = ["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"] -> [333, -45]

# "I -45": -45 삽입
# "I 653": 653 삽입 
# "D 1": 최댓값(653) 삭제, -45가 남아있음
# "I -642": -642 삽입
# "I 45": 45 삽입
# "I 97": 97 삽입 
# "D 1": 최댓값(97) 삭제
# "D -1": 최솟값(-642) 삭제, -45와 45가 남아있음
# "I 333": 333 삽입, 이중 우선순위 큐에 -45, 45, 333가 남아있음

# => [333, -45]

 

 

## 의사코드 ##

# 최대/최솟값 찾기 -> heapq

# for o in operations:
#     if o.startswith('I'):
#         이중 우선순위 큐에 int(o.split()[1]) 삽입 -> 문자열로 되어 있어서 int()로 변환해줘야 함
#     else:
#         if len(이중 우선순위 큐) == 0: # 비어있으면
#             continue # 해당 연산 무시
#         elif o == "D 1":
#             이중 우선순위 큐에서 최댓값 삭제
#         else: # -> o == "D -1"
#             이중 우선순위 큐에서 최솟값 삭제

# if len(이중 우선순위 큐) == 0: # 비어있으면
#     return [0,0]
# else:
#     return [최댓값, 최솟값]

 

 

 

통과한 코드

 

import heapq

def solution(operations):
    heap = [] # 이중 우선순위 큐

    for o in operations:
        # 명령어가 'I'인 경우
        if o.startswith('I'):
            heapq.heappush(heap, int(o.split()[1])) # 숫자를 int()로 변환한 후 이중 우선순위 큐에 삽입
        # 명령어가 최댓값/최솟값 삭제인 경우
        else:
            # 이중 우선순위 큐가 비어있으면 해당 연산 무시
            if len(heap) == 0:
                continue
            # 명령어가 최댓값 삭제이면
            elif o == 'D 1':
                heap.remove(heapq.nlargest(1, heap)[0]) # 이중 우선순위 큐에서 최댓값 삭제
            # 명령어가 최솟값 삭제이면
            else:
                heapq.heappop(heap) # 이중 우선순위 큐에서 최솟값 삭제
    # 모든 연산을 처리한 후 이중 우선순위 큐가 비어있으면 [0,0] 반환
    if len(heap) == 0:
        return [0,0]
    # 이중 우선순위 큐가 비어있지 않으면
    else:
        return [heapq.nlargest(1, heap)[0], heap[0]] # [최댓값, 최솟값] 반환

-> 최댓값은 heapq.nlargest(1, heap)으로 구하고, 최댓값 삭제는 remove() 활용

 

 

• 최소 힙인 heapq에서 최댓값 구하기 
  • heapq.nlargest(n, list)
    • -> list에서 가장 큰 n개의 수를 뽑아 리스트로 반환 
  • 최댓값 1개 구하기 
    • => heapq.nlargest(1, list)

 

# 최소 힙인 heapq에서 최댓값 구하기 
# heapq.nlargest(n, list) -> list에서 가장 큰 n개의 수를 뽑아 리스트로 반환 
import heapq
heap = [-45, 45, 333]
heapq.nlargest(1, heap)

"""
[333]
"""

# 최소 힙에서 최댓값 삭제하기
import heapq
heap = [-45, 45, 333]
print('삭제 전:', heap)
print('최댓값:', heapq.nlargest(1, heap)[0]) # 최댓값
heap.remove(heapq.nlargest(1, heap)[0]) # heap 리스트에서 최댓값 삭제
print('삭제 후:', heap)

"""
삭제 전: [-45, 45, 333]
최댓값: 333
삭제 후: [-45, 45]
"""

# cf) n을 len(heap)으로 하면 내림차순 정렬됨
heapq.nlargest(len(heap), heap)

"""
[333, 45, -45]
"""

 

 

 

• 과정 확인

# operations = ["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]

"""
I 16
[16] 

I -5643
[-5643, 16] 

D -1
최솟값: -5643
[16] 

D 1
최댓값: 16
[] 

D 1

I 123
[123] 

D -1
최솟값: 123
[] 

--------------------------------------------------
[]
--------------------------------------------------

[0, 0]
"""

# operations = ["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]

"""
I -45
[-45] 

I 653
[-45, 653] 

D 1
최댓값: 653
[-45] 

I -642
[-642, -45] 

I 45
[-642, -45, 45] 

I 97
[-642, -45, 45, 97] 

D 1
최댓값: 97
[-642, -45, 45] 

D -1
최솟값: -642
[-45, 45] 

I 333
[-45, 45, 333] 

--------------------------------------------------
[-45, 45, 333]
--------------------------------------------------

[333, -45]
"""

 

 

 

다른 풀이

 

import heapq

def solution(arguments):
    res = [] # 이중 우선순위 큐
    for argument in arguments:
        cmd, v = argument.split(' ') # 명령어, 데이터
        i = int(v)
        if cmd == 'I':
            heapq.heappush(res, i)
        elif cmd == 'D' and res:
            # "D -1"인 경우
            if i < 0:
                heapq.heapify(res)
                heapq.heappop(res)
            # "D 1"인 경우
            else:
                heapq._heapify_max(res)
                heapq._heappop_max(res)
    return [max(res), min(res)] if res else [0, 0]

-> 최댓값은 heapq._heapify_max()로 구하고, 최댓값 삭제는 heapq._heappop_max() 활용

 

• heapq._heapify_max()
  • 최소 힙을 내림차순으로 정렬
  • => heapq.nlargest(len(heap), heap) 한 거랑 같은 결과
• heapq._heappop_max()
  • 최소 힙에서 최댓값 삭제
• 둘 다 push 불가
  • -> 계속 데이터를 삽입해야 하는 경우에 사용할 수 없음
• 이미 최소 힙으로 정렬된 상태에서 최댓값을 찾는 것이기 때문에 온전히 최대 힙을 구현하는 건 아님

# heapq._heapify_max() 
# -> 최소 힙을 내림차순으로 정렬 (== heapq.nlargest(len(heap), heap))
import heapq
heap = [-45, 45, 333]
heapq._heapify_max(heap)
heap

"""
[333, 45, -45]
"""

# heapq._heappop_max()
# -> 최댓값 삭제
heapq._heappop_max(heap)
heap

"""
[45, -45]
"""

 

 

 

 

 

heapq로 최대 힙 구현하기

• 1) (우선 순위, 값)으로 튜플 형태로 추가

from heapq import heappush, heappop

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heappop(heap)[1])  # index 1
  
"""
8
7
5
4
3
1
"""

-> 힙에 튜플(tuple)를 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용한 것

 

각 값에 대한 우선 순위를 구한 후, (우선 순위, 값) 구조의 튜플(tuple)을 힙에 추가하거나 삭제하면 됨

 

힙에서 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값을 취하면 됨 (우선 순위가 인덱스 0이고, 값이 인덱스 1)

 

 

• 2) 부호를 변경해서 추가

import heapq

heap = []
values = [1,5,3,2,4]

for value in values:
	heapq.heappush(heap, -value)
    
"""
heap = [-5,-4,-3,-1,-2]
"""

# 큰 숫자부터 출력
for i in range(5):
	print(-heapq.heappop(heap))
    
"""
5
4
3
2
1
"""

-> 부호를 바꿔서 최소 힙에 넣어준 다음, 최솟값부터 pop을 해줄 때 다시 부호를 바꿔서 최댓값부터 pop되도록 한 것

 

 

 

 

참고)

 

https://www.daleseo.com/python-heapq/

파이썬의 heapq 모듈로 힙 자료구조 사용하기

 

https://docs.python.org/3/library/heapq.html

heapq — Heap queue algorithm

 

https://velog.io/@yyj8771/Python-heapq%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EC%B5%9C%EC%86%8C-%ED%9E%99-%EC%B5%9C%EB%8C%80-%ED%9E%99

[Python] heapq를 이용한 최소 힙, 최대 힙

 

https://sirzzang.github.io/programming/Programming-heapq/

[Python] heapq 모듈