[프로그래머스/PYHTON]이중우선순위 큐_힙(heap)

 

 

 

 

 

 

 

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

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

 

 

풀이법 : 

 

 

 

 

1. 띄어쓰기를 기준으로 나눈다.

 

2- 1. I 라면 Insert 

2- 2. D라면 Delete

      2-2-1 : 만약 아무것도 없다면 pass!! (pop할 숫자가 없으므로) 

      2-2-1 : 1 이라면 최댓값 pop ( nlargest 이용) 

      2-2-2 : 최솟값 pop

 

3. heap이 비었다면 [0,0]을 , 비어있지 않다면 max, min값을 answer에 넣는다. 

 

 

 

 

---

 

 

 

코드 : 

 

import heapq
def solution(operations):
    heap = [] #  heap
    answer = []
    
    for i in  operations :
        cur = i.split() # 띄어쓰기를 기준으로 나눔 
        
        if cur[0] == 'I' : # insert
            heapq.heappush(heap,int(cur[1]))
            
        else : # delete
            if len(heap) == 0:  # delete를 해야하는데 비어있다면 PASS or cotinue 가능
                pass 
            elif cur[1] == '1' : # 최댓값 제거 
                heap = heapq.nlargest(len(heap),heap)[1:]
                heapq.heapify(heap) # 엉클어진 순서를 제대로
            elif cur[1] == '-1' : # 최솟값 제거
                heapq.heappop(heap)
    if heap:
       answer.append(max(heap)) 
       answer.append(min(heap))    
       
    else : 
        zero = [0,0]
        answer.extend(zero)
    return answer

 

<이렇게도 answer에 max, min값을 넣을 수 있다>

import heapq
def solution(operations):
    answer = []
    heap = []
    for i in operations :
        cur = i.split()
        if cur[0] == "I" :
            heapq.heappush(heap,int(cur[1]))
        else : # cur[0] == "D"
            if len(heap)==0 : continue
            elif cur[1] == "1" : # 최댓값 삭제 
                heap = heapq.nlargest(len(heap), heap)[1:]
                heapq.heapify(heap)
            else : # 최솟값 삭제 
                heapq.heappop(heap)
    if heap :
        Max = max(heap)
        Min = min(heap)
        ans = [Max,Min]
        answer.extend(ans)
        
    else : # heap이 비었을 경우 
        answer.append(0)
        answer.append(0)
            
    return answer

 

---

 

 

 

배운 점 : 

 

1 . heap의 heapify의 역할

리스트를 만든 후 차곡차곡 heappop , heappush를 해야지 리스트가 heap형태로 유지되는것이다.

elif에서 최댓값을 제거하였을 때 

리스트의 순서가 뒤틀렸다.

이때 heapify를 통해 순서를 제대로 맞추어야지 정답이다. 

 

 

2. heapq의 nlargest

이것을 통해 해당 힙에서 큰 순서대로 정렬해서 가져올 수 있다. 

 

 

3. pass와 continue는 다르다.

 

pass는 정말 아무것도 안하고 넘긴다는 의미고 continue는 for문에서 다음으로 넘어간다는 의미이다. 

 

import heapq
def solution(operations):
    answer = []
    heap = []
    for oper in operations :
        oper = oper.split()
        if oper[0]=="I" :
            heapq.heappush(heap, int(oper[1]))
        else :
            if len(heap)==0 :
                pass
            if oper[1] == "1":
                heap = heapq.nlargest(len(heap), heap)[1:]
                heapq.heapify(heap)
            else :
                heapq.heappop(heap)
    if len(heap) == 0 :
        answer.append(0)
        answer.append(0)
    else :
        answer.append(max(heap))
        answer.append(min(heap))
            
    return answer

이 코드는 틀린다. 

pass를 한다면 다음 if가 실행될 수 있기때문이다. 

 

 

이 경우 

1) if oper[1] == "1" : 에서 elif로 바꾸거나 

2) pass에서 continue로 바꾸면 된다. 

 

 

 

 

참고 블로그 : 

https://velog.io/@norighthere/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Python-%EC%9D%B4%EC%A4%91%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84%ED%81%90

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

 

 

복습 : 

 

✅ 20220618

✅ 20220620

✅ 20220622

✅ 20220626

✅ 20220630