[알고리즘/파이썬] 프로그래머스 - 이중우선순위큐

문제

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

프로그래머스

 

 

풀이

예전에도 풀었던 문제인데 ... 예전 풀이를 먼저 보고 충격을 받았다.

최소 최댓값을 뽑으라고하면 이제는 Heap이 가장 먼저 떠오르는데... ㅋㅋ ㅠㅠ 당시엔 그렇지 않나보다

from collections import deque
def solution(operations):
    q=deque()
    
    for cmd in operations:
        if cmd[0]=="I":
            q.append(int(cmd[2:]))
        elif cmd=="D 1" and len(q)>0:
            q=deque(sorted(q))
            q.pop()
        elif len(q)>0:
            q=deque(sorted(q))
            q.popleft()
            
    if len(q)==0:
        return [0,0]
    else:
        q=sorted(q)
        return [q[-1],q[0]]

너무나 충격적인 무지성 코드다.

그때그때 솔트해서 최솟값 최댓값을 없애는 식으로 구현을..했더라 쩝

이 문제가 테케도 되게 적고 부실(?)한 거 같은데 그래서 통과한거지 heap을 의도로 만든 문제였으면 매번 솔팅하는 거 때문에 무조건 시간 초과가 나지 않았을까 싶다

 

아무튼 요번엔 heapq를 사용해서 풀었고, 최대힙 최소힙을 따로따로 구현해야 하나..? 하다가 따로 구현했을 시에 다른 큐에서 일어난 일을 다른 큐에 어떤식으로 적용해야할지 감도 안 잡히고.. 그래서 하나의 힙으로 구현을 했다. 

최소힙으로 구현을 했고, 최댓값을 빼야 할때는 heapq의 nlargest메소드를 사용했다. 해당 메소드를 사용하면 내림차순 배열이 반환된다. 첫번째 인자로는 가장 큰 애들 몇개를 뽑아올건지, 두번째 인자로는 최댓값을 뽑아오길 바라는 배열을 넣으면 된다. 물론 이렇게 반환한다고 해서 반환한 값들이 heap에서 pop되는게 아니라는 점을 유의해야 한다. 

 

나는 첫번째 인자로 배열의 길이, 두번째 인자로 배열을 넣어줬다. 저러면 내림차순 정렬된 배열이 나오기 때문에 그 중 가장 큰 값인 0번째 인덱스값을 제외한 배열을 만든 후 다시 heapify로 heap을 구현해주면 우리가 원했던 최댓값 pop 기능이 구현된 것이다.

 

 

 

코드

import heapq
def solution(operations):
    q = []
    for a in operations:
        c, n = a.split()
        if c == 'I':
            heapq.heappush(q,int(n))
            continue
        if q:
            if c=='D' and n == "1":
                q = heapq.nlargest(len(q),q)[1:]
                heapq.heapify(q)
            else:
                heapq.heappop(q)           
    if not q:
        return [0,0]
    else:
        max_value = heapq.nlargest(1,q)[0]
        min_value = heapq.heappop(q)
        return [max_value,min_value]