프로그래머스 42628 이중우선순위큐 파이썬 풀이

난이도 : Lv. 3

풀이일 : 2410292

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

프로그래머스

---

문제

---

아이디어

• 최소힙과 최대힙 두 개를 각각 운영하며, 한 쪽에서 삭제된 요소인지 여부를 확인할 배열을 두고, 이중우선순위 큐로 사용한다.
• 삭제 연산 시, 유효한 숫자인지 확인하는 과정을 거친다.

---

전체 코드

import heapq

def pop(queue, arr): # 이중우선순위 큐 pop 연산
    while queue:
        num, index = heapq.heappop(queue)
        if arr[index]: # 유효성 검사
            return num, index
    return 0, 0 # 이중우선순위 큐가 비어있을 경우

def solution(operations):
    answer = []
    minq, maxq = [], [] # 최소힙, 최대힙
    check = [False] * (len(operations) + 1) # 유효성
    
    for i in range(1, len(operations) + 1):
        alphabet, num = map(str, operations[i - 1].split())
        if alphabet == "I": # 숫자 추가
            heapq.heappush(minq, (int(num), i))
            heapq.heappush(maxq, (-int(num), i))
            check[i] = True
        else:
            if num == "1": # 최대힙 삭제
                check[pop(maxq, check)[1]] = False
            else: # 최소힙 삭제
                check[pop(minq, check)[1]] = False
    
    answer.append(-pop(maxq, check)[0]) # 최댓값
    answer.append(pop(minq, check)[0]) # 최솟값
    
    return answer

---

상세 풀이 코드

import heapq

def pop(queue, arr):
    while queue:
        num, index = heapq.heappop(queue)
        if arr[index]:
            return num, index
    return 0, 0

• 이중우선순위큐에서 요소를 삭제하는 함수다.
• 주어지는 큐와 유효성을 저장할 check 배열을 확인하며, 이중우선순위큐에 남아있는 숫자와, 해당 숫자의 check 인덱스를 반환한다.
• 만약, 큐가 비어있다면 0, 0을 반환한다.

 

def solution(operations):
    answer = []
    minq, maxq = [], []
    check = [False] * (len(operations) + 1)

• minq, maxq는 각각 최소힙, 최대힙
• check 배열은 삭제 여부를 판단할 배열이다. 인덱스 0은 pop 함수에서 0을 반환할 경우에 사용한다.
• operations 배열의 길이 + 1로 크기를 지정한다.

 

    for i in range(len(operations)):
        alphabet, num = map(str, operations[i].split())
        if alphabet == "I":
            heapq.heappush(minq, (int(num), i + 1))
            heapq.heappush(maxq, (-int(num), i + 1))
            check[i + 1] = True

• operations로 주어진 입력을 처리한다.
• 주어지는 alphabet이 I라면 minq, maxq에 주어진 숫자와 인덱스를 추가한다.
• 이 때, check 배열에 인덱스 0은 사용하지 않을 것이므로, i + 1을 인덱스로 추가한다.
• check[i + 1]도 유효한 숫자라고 설정을 변경해준다.

 

      else:
            if num == "1":
                check[pop(maxq, check)[1]] = False
            else:
                check[pop(minq, check)[1]] = False

• 삭제 명령에 해당하는 경우, 최댓값 혹은 최솟값을 삭제한다.
• pop 함수를 통해 유효한 최댓값 혹은 최솟값을 찾고, 그 인덱스를 삭제해준다.

 

    answer.append(-pop(maxq, check)[0])
    answer.append(pop(minq, check)[0]) 
    
    return answer

• 반복문이 종료된 후, 최댓값과 최솟값을 찾아 answer에 추가한다.
• 최종적으로 answer를 리턴한다.

---

느낀점

• 오랜만에 힙큐를 써서 어색한 느낌으로 풀었다. 풀었던 유형들도 반복해줘야할 것 같다.
• 이제 다른 언어로도 풀어봐야지