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

문제

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

코딩테스트 연습 - 이중우선순위큐

---

풀이

 

힙 카테고리에 있어서 힙으로 만들어 풀어야겠다고 생각했다.

힙은 최소, 최대 힙 중 하나로 만들어져야 하는데 문제에서는 최대와 최소를 모두 삭제할 수 있어야 했다.

 

그래서 최대 힙, 최소 힙 총 2개를 만들고 만약 최대값 삭제 시 최대 힙의 값을 최소 힙에서 검색해서 삭제하는 방식으로 풀어야하나? 싶었는데 로직이 깔끔하지 못한 느낌이고 비효율적일 것 같았다.

 

이런저런 고민을 해보다가 그냥 힙 버리고 냅다 풀어보기로 했다.

 

def solution(operations):
    q = []
    
    for o in operations:
        op = o.split()
        if op[0] == 'I':
            q.append(int(op[1]))
        elif op[0] == 'D':
            if len(q) == 0:
                continue
            elif op[1] == '1':
                q.remove(max(q))
            else:
                q.remove(min(q))
    
    return [max(q) if q else 0, min(q) if q else 0]

그런데 웬걸,, 효율성 테스트같은게 있을 줄 알았는데 그런거 없고 그냥 통과했다.

 

---

다른 사람의 풀이

 

분명 문제에서는 이걸 의도한 것이 아니었을 것 같았고 내 풀이는 실제 코테에선 통과하지 못할 것 같았다.

 

from heapq import heappush, heappop

def solution(arguments):
    max_heap = []
    min_heap = []
    for arg in arguments:
        if arg == "D 1":
            if max_heap != []:
                heappop(max_heap)
                if max_heap == [] or -max_heap[0] < min_heap[0]:
                    min_heap = []
                    max_heap = []
        elif arg == "D -1":
            if min_heap != []:
                heappop(min_heap)
                if min_heap == [] or -max_heap[0] < min_heap[0]:
                    max_heap = []
                    min_heap = []
        else:
            num = int(arg[2:])
            heappush(max_heap, -num)
            heappush(min_heap, num)
    if min_heap == []:
        return [0, 0]
    return [-heappop(max_heap), heappop(min_heap)]

내가 처음 생각했던 것처럼 max힙과 min 힙을 두개 만들어 연산한 코드이다.

그런데 두 힙의 동기화 과정이 없어 틀렸다는 말도 있다.

 

import heapq

def solution(operations):
    heap = []

    for operation in operations:
        operator, operand = operation.split(' ')
        operand = int(operand)

        if operator == 'I':
            heapq.heappush(heap, operand)
        elif heap:
            if operand < 0:
                heapq.heappop(heap)
            else:
                heap.remove(max(heap))

    if not heap:
        return [0, 0]

    return [max(heap), heap[0]]

다른 코드.

이건 최소힙을 만들고 최댓값은 remove로 제거했다.

 

다른 글에서는 heapq.nlargest(n, list)을 사용해 정렬하고 다시 최소힙을 만들기도 했다

뭔가 이거다 싶게 깔끔한 로직은 없었다.

애초에 효율성 테스트도 없는 문제라 그런가 싶다.