[프로그래머스] Level 3_이중우선순위큐(힙)

📌문제 유형

힙(Heap)

 

📌문제

프로그래머스

 

📌나의 문제풀이

1차 시도(66.7)

import heapq

def max_heap(min_heapq):
    max_heapq = []
    num_list = []
    
    if min_heapq == []:
        return num_list
    
    for item in min_heapq:
        heapq.heappush(max_heapq,(-item,item))
        
    heapq.heappop(max_heapq)
    
    while max_heapq:
        heapq.heappush(num_list, heapq.heappop(max_heapq)[1])
    
    return num_list
    

def solution(operations):
    answer = []
    num_list = []
    
    for num in operations:
        # 값 넣기
        if num.startswith('I'):
            num = num.replace('I','')
            heapq.heappush(num_list, int(num))
        elif num.startswith('D'):
            # 최솟값 삭제
            if int(num.replace('D','')) == -1:
                heapq.heappop(num_list)
            # 최댓값 삭제
            else:
                num_list = max_heap(num_list)
                
    # num_list에서 최댓값, 최솟값 순서대로 answer에 넣기
    if list(num_list) == []:
        return [0,0]
    else:
        answer.append(max(list(num_list)))
        answer.append(min(list(num_list)))
        return answer

2차 시도(성공)

- 실패요인 : 최솟값 삭제할 때, 빈 큐에 데이터 삭제연산이 있으면 무시하라는 조건이 없어서 런타임 에러 발생

• heapq 만들기
• (값 넣기) startswith, replace, strip 이용하여 heapq에 값 넣기
• (값 삭제) 
  • 최솟값 삭제 : heapq.heappop() 이용
  • 최댓값 삭제 : max_heap 함수 정의 -> 최대 힙 구현 후 최댓값 삭제, 새로운 리스트에 최대 힙 넣기
• (answer 출력) [최댓값, 최솟값] 출력

import heapq

def max_heap(min_heapq):
    max_heapq = []
    num_list = []
    
    # 빈 큐에 데이터 삭제, 해당 연산 무시
    if min_heapq == []:
        return num_list
    
    # 최대 힙 만들고 최댓값 제외
    for item in min_heapq:
        heapq.heappush(max_heapq,(-item,item))
    heapq.heappop(max_heapq)
    
    # 최대 힙 구성형태 [(-9,9),(-4,4),(5,-5)] -> 원래 값은 [1]에 있는 값
    # 원래 값들로만 구성된 리스트 생성
    while max_heapq:
        heapq.heappush(num_list, heapq.heappop(max_heapq)[1])
    
    return num_list
    

    
def solution(operations):
    answer = []
    num_list = []
    
    for num in operations:
        # 값 넣기
        if num.startswith('I'):
            num = num.replace('I','')
            num = num.strip()
            heapq.heappush(num_list, int(num))
        elif num.startswith('D'):
            # 최솟값 삭제
            if num == 'D -1':
                # 빈 큐에 데이터 삭제 연산, 무시하기
                if num_list == []:
                    continue
                else:
                    heapq.heappop(num_list)
            # 최댓값 삭제
            else:
                num_list = max_heap(num_list)
                
    # num_list에서 최댓값, 최솟값 순서대로 answer에 넣기
    if list(num_list) == []:
        return [0,0]
    else:
        answer.append(max(list(num_list)))
        answer.append(min(list(num_list)))
        return answer

 

📌리뷰

 - 문제의 조건 잘 보기

 - 최대 힙 구현 익히기

 - 공백 제거

[python] 파이썬 공백 제거 (replace, strip) 2가지 방법