Lv.3 이중우선순위큐

코딩테스트 연습 - 이중우선순위큐 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

힙도 공부해 보았으니 한 번 테스트해봐야지

 

겁 없이 레벨 3에 한 번 도전해보았다.

근데 생각보다 별로 어렵진 않았음. 그래도 정답률이 꽤 높아서 그런가

코드도 어렵지 않게 짰기 때문에 쉽게 이해할 수 있을 듯

 

1. 큐 개념을 사용한 해결법

def solution(o):
    q = []
    while o:
        so = o.pop(0)
        stro, into = so.split()
        into = int(into)
        if stro=='I':
            q.append(into)
        elif stro=='D' and into==1:
            if q:
                del q[q.index(max(q))]
        elif stro=='D' and into==-1:
            if q:
                del q[q.index(min(q))]

    if q:
        return [max(q), min(q)]
    else:
        return [0,0]

 

하지만 보다 힙을 사용해보고 싶었기 때문에

다른 코드로도 풀어보았다.

 

2. 힙 개념을 사용한 풀이법 

import heapq

def solution(operations):

	# 빈 리스트 answer, 최소 힙 minHeap, 최대 힙 maxHeap을 생성
    answer = []
    maxHeap = []
    minHeap = []

    for n in operations:
    	# 각 n을 공백을 기준으로 분할하여 words에 저장
         words = n.split(" ")

         if words[0] == "I":
         	# words[1] 값을 최소 힙 minHeap과 최대 힙 maxHeap에 추가
            # 최소 힙에는 값을 그대로, 최대 힙에는 음수로 변환하여 값을 추가
             heapq.heappush(minHeap,int(words[1]))
             heapq.heappush(maxHeap,(-int(words[1]),int(words[1])))
         elif int(words[1]) == 1 and minHeap:
         	# 최대 힙에서 가장 큰 값을 제거
             minHeap.remove(heapq.heappop(maxHeap)[1])
         elif minHeap:
             minValue = heapq.heappop(minHeap)
             maxHeap.remove((-minValue, minValue))
	# 최대 힙 maxHeap이 비어있지 않은 경우, 최대 힙에서 가장 큰 값을 가져옴
    # 해당 값의 두 번째 요소는 원래 값이므로, answer에 추가함
    if maxHeap:
       answer.append(heapq.heappop(maxHeap)[1])
    else:
       answer.append(0)
    if minHeap:
        answer.append(heapq.heappop(minHeap))
    else:
        answer.append(0)

    return answer

 

heapq 모듈이 어색하신 분은 아래 링크를 타주시면 될 것 같다.

https://www.youtube.com/watch?v=tyslgaqcJ0c

 

 

 

아니 왜 2점밖에 안 줌 어이없

 

자려고 3레벨 문제 풀었는데 잠이 안 온다..