[프로그래머스 - heap] 더 맵게

programmers.co.kr/learn/courses/30/lessons/42626

 

로직

한 turn에 데이터를 pop한 후 새로운 데이터로 push하는 과정이 모두 들어가있고,

리스트는 항상 정렬상태여야한다.

 

이 상황에서 가장 적절한 데이터 구조는 heap이라고 생각하여 heapq 내장 모듈을 사용하였다.

 

1. heapify 하여 scoville 리스트를 heap 형식으로 만들어준다.

2. scoville의 길이가 0이 아니라면 아래의 과정을 반복한다.

• [pop] x = heappop()
• if x > K라면 [pop] y도 pop한 다음 [new_scoville = x + y*2] 연산을 해준다.
  • [push] new_scoville를 heap에 넣어준다.
• else 모든 데이터가 K보다 크거나 같으므로 목표 달성! return answer

 

 

 

코드

import heapq

def solution(scoville, K):
    answer = 0

    heapq.heapify(scoville)

    while scoville:
        try:
            x = heapq.heappop(scoville)
            if x < K:
                y = heapq.heappop(scoville)
                new_scoville = x + y * 2
                heapq.heappush(scoville, new_scoville)
                answer += 1
            else:  # x >= K
                return answer

        except:
            return -1

 

 

 

 

TIP

heapq

- heapq은 파이썬에서 기본으로 제공하는 heap 형식 내장모듈이다.

 

만약 h가 정렬하고자 하는 list라면

import heapq
# min heap이 기본형이다.

h = [1,2,3,]

heapq.heapify(h) # make as a heap
heapq.heappop() # pop 1
heapq.heappush(h, 1) # push 1

 

 

코딩테스트 연습 - 더 맵게