프로그래머스 - 더 맵게

1. 문제

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

코딩테스트 연습 - 더 맵게

2. 소스코드 (Python3)

import heapq   def solution(scoville, K):     answer = 0     scoville = [s for s in scoville]     heapq.heapify(scoville)         while True:         tmp1 = heapq.heappop(scoville)         if tmp1 >= K: break         if not scoville: return -1         tmp2 = heapq.heappop(scoville)         heapq.heappush(scoville, tmp1 + 2*tmp2)         answer += 1            return answer

 

3. 고찰

1) 시간 복잡도

<힙 연산 시간복잡도>

- 구성 heapify : O(N log N)

- 삽입 insert : O(log N)

- 삭제 remove : O(log N)

 

<소스코드 시간복잡도>

heapify -> O(N log N)

while loop -> 최대 N-1번 반복

    힙 insert 두 번 -> O(2*log N)

    힙 remove 한 번 -> O(log N)

따라서 위 소스코드의 시간 복잡도는 O(N log N)이다.