[프로그래머스] 이중우선순위큐 - 파이썬(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]를 반환합니다.

 

 

나의 풀이

from heapq import heapify, heappush, heappop, nlargest, nsmallest

def solution(operations):
    q = []
    for i in operations :
        if i[0] == 'I':
            heappush(q, int(i[2:]))
        elif q != [] :
            if i == "D 1" :
                q.remove(nlargest(1, q)[0])
                heapify(q)
            elif i == 'D -1' :
                heappop(q)
                
    return [0,0] if q==[] else [nlargest(1,q)[0],q[0]]

• 최댓값, 최솟값을 구하는 문제이므로 heap 을 사용하였다.
• I로 시작하는 경우, 뒤에 나오는 숫자를 heap 에 push 한다.
• D 1일 경우, 최댓값을 삭제해야 한다. 따라서 nlargest() 를 이용해서 q에서 1개의 가장 큰 요소로 구성된 리스트를 반환받고, [0] 으로 원소를 추출하였다. 
• 다음으로, remove() 함수를 이용하여 해당하는 원소를 q에서 삭제하였다.
• remove() 로 해당 원소를 삭제한 경우, 힙 구조가 유지되지 않으므로 heapify() 로 힙을 재정렬 해준다.
• D -1 의 경우, 최솟값을 삭제해야 하므로 최소힙으로 구현된 q에서 pop(0) 을 해주었다.

* 최소힙의 경우, 첫번째 노드는 최솟값임이 보장되나 그 외의 노드들은 자식 노드보다 크기만 하면 된다.

  즉, 마지막 원소가 최댓값이라는 보장이 없다!

 

 

다른 풀이

나는 nlargest 를 사용해서 최댓값을 얻었는데, 사실 이보다 정석적인 풀이는 최소힙과 최대힙을 동시에 구현하는 것이다.

이를 위해서는, 최대힙에서 삭제되면 최소힙에서도 삭제가 되어야 한다. 

따라서 각 힙에 원소를 삽입할 때 (값, 인덱스) 형태의 튜플로 삽입한다.

또한, 해당 원소가 삭제되었음을 알리기 위해 문제에 주어진 문자열의 최대 길이 조건인 1,000,000 개 만큼의 배열을 만들어놓고, 모든 원소를 True 로 초기화한다. 만약 힙에서 삭제되었다면 해당 인덱스에 False 로 값을 변경할 것이다.

그리고, 다른 힙에서 삭제되었는지의 여부를 해당 배열에서 확인할 수 있다.

from heapq import heappush, heappop

def solution(operations):
    visited = [False] * 1000001 # 모두 삭제된 것으로 초기화
    min_heap,max_heap = [],[]
    
    for i in range(len(operations)) : 
        operation, number = operations[i].split()
        if operation == 'I' :
            heappush(min_heap, (int(number), i))
            heappush(max_heap, (-int(number), i)) # 최대힙에는 음수로 삽입
            visited[i] = True # 삽입되었으므로 해당 인덱스에 True 로 변경
            
        else :
            if number == "1":
                while max_heap and not visited[max_heap[0][1]] :
                    heappop(max_heap) # 첫번째원소가 다른 힙에서 삭제된 것이라면, 계속 pop
                if max_heap :
                    visited[max_heap[0][1]] = False # 삭제되었음을 알리기 위해 false 로 변경
                    heappop(max_heap)
            elif number == "-1" :
                while min_heap and not visited[min_heap[0][1]] : 
                    heappop(min_heap)
                if min_heap :
                    visited[min_heap[0][1]] = False
                    heappop(min_heap)
      
    while max_heap and not visited[max_heap[0][1]] : ) # 첫번째원소가 다른 힙에서 삭제된 것이라면, 계속 pop
        heappop(max_heap)
    while min_heap and not visited[min_heap[0][1]] :
        heappop(min_heap)
    
    # [] 가 아니라면, 첫 번째 원소가 삭제되지 않은 원소를 뜻하므로 힙이 비어있지 않은것
    # 최대힙의 원소는 부호를 반대로 변경하기
    return [0,0] if min_heap==[] or max_heap==[] else (-max_heap[0][0], min_heap[0][0])

 

visited 로 두개의 힙을 동기화하는 방법!! 잊지말자.