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

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

프로그래머스

아이디어

• operations의 각 요소를 split() 처리해주어 삽입과 삭제를 판단.
• heapq를 활용하여 삽입은 자동처리
• -1, 1 확인 후 최솟값 최댓값 둘 중 뭘 뺄지 판단

코드(틀림)

import heapq

def solution(operations):
    heap = []
    for i in operations:
        # 삽입 삭제 분리
        a, b = i.split()

        # 삽입은 heapq를 통해 자동 정렬
        if a == "I":
            heapq.heappush(heap, int(b))

        # 삭제
        else:
            # 빈 배열이면 무시
            if len(heap) == 0:
                continue
            # 최댓값
            elif int(b) == 1:
                heap.pop()
            # 최솟값
            else:
                heapq.heappop(heap)
                
    # 빈 배열이면 0,0 반환
    if not heap:
        return [0, 0]
    # 최댓값 최솟값 반환
    else:
        s = heapq.heappop(heap)
        b = heap.pop()
        return [b, s]

• 흠 테스트 3은 틀리게 나온다.
• 어떤 반례가 있는 거지?

해결시도(틀림)

• 배열에 삽입이 단 한 번만 이루어진다면 오류가 나는 것을 발견했다.
• 이때에 예외처리를 해주면 될 듯하다.

import heapq

def solution(operations):
    heap = []
    for i in operations:
        # 삽입 삭제 분리
        a, b = i.split()

        # 삽입은 heapq를 통해 자동 정렬
        if a == "I":
            heapq.heappush(heap, int(b))

        # 삭제
        else:
            # 빈 배열이면 무시
            if len(heap) == 0:
                continue
            # 최댓값
            elif int(b) == 1:
                heap.pop()
            # 최솟값
            else:
                heapq.heappop(heap)
    # 빈 배열이면 0,0 반환
    if not heap:
        return [0, 0]
    # 최댓값 최솟값 반환
    elif len(heap) == 1:
        a = heap.pop()
        return[a, a]
    else:
        s = heapq.heappop(heap)
        b = heap.pop()
        return [b, s]

• 그래도 똑같이 3번 테스트에서 실패가 뜬다..

해결방법(정답)

• 찾아보니 heapq에 단순히 pop() 연산은 최댓값을 가져온다는 보장이 없다고 한다.
• 최대 최솟값을 구하는 로직을 max와 min을 이용하여 고쳐야 한다.

코드(정답)

import heapq

def solution(operations):
    heap = []
    for i in operations:
        # 삽입 삭제 분리
        a, b = i.split()

        # 삽입은 heapq를 통해 자동 정렬
        if a == "I":
            heapq.heappush(heap, int(b))

        # 삭제
        else:
            # 빈 배열이면 무시
            if len(heap) == 0:
                continue
            # 최댓값
            elif int(b) == 1:
                heap.pop()
            # 최솟값
            else:
                heapq.heappop(heap)
    # 빈 배열이면 0,0 반환
    if not heap:
        return [0, 0]
    # 최댓값 최솟값 반환
    else:
        return [max(heap), min(heap)]

마무리

• heapq의 삽입 삭제 방법 및 최솟값을 추출하는 코드가 오랜만이라 기억이 나지 않아 찾아보았다.
• deque처럼 익숙하게 사용하도록 노력해야겠다.
• heapq를 통해 자동 정렬된 배열에서 pop() 연산을 해서 얻은 값이 무조건 최댓값이 아니라고 인지하도록 하자 !!