[힙] 프로그래머스 이중우선순위큐 파이썬

김아현·2023년 5월 5일
0

코딩테스트

목록 보기
7/26
post-thumbnail

이중우선순위큐 파이썬 풀이

접근 방법

문제 상에서 operation의 최대값과 최소값을 Delete하는 연산엔 pop과 heappop을 섞어 풀면 되지않을까 싶어서 요구사항대로, 케이스별로 풀었다.

1차 작성 코드

import heapq as hq

def solution(op):
        q = []
        for i in op:
            ins, num = i.strip().split() 
            if ins == 'I':
                hq.heappush(q, int(num))
            elif ins == 'D' and q:
                if num == '-1':
                    hq.heappop(q)
                elif num == '1':
                    q.pop()
        return [max(q), min(q)] if q else [0,0]

operation이 op라는 배열로 주어졌을 때, 각 명령어의 문자인 instruction과 숫자부 number를 나누어 ins, num 변수에 할당했다.
그리고 각각의 문자를 조건에 넣고 명령대로 수행했다.

1차 코드 문제점

이 문제의 다른 풀이를 보면, 노드를 직접 구현한 걸 볼 수 있다. 내가 작성한 1차 코드처럼 풀면 heap 트리 구조가 유지되지 않는다고 한다.
예를 들어 ["I 6", "I 2", "I 1", "I 4", "I 5", "I 3", "D 1", "I 7", "D -1", "I 6", "D -1", "D -1"] 라는 테스트 케이스에 대해서 프로그램은 [7,4]를 리턴해야한다. 하지만, 내 프로그램은 [7,5] 를 리턴한다.

profile
멘티를 넘어 멘토가 되는 그날까지 파이팅

0개의 댓글