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

 문제

 

 

 문제 상황

 

- 가장 작은 요소들을 꺼내 변화를 주면서 다시 넣는 구조이다.

 

- 가장 작은 요소를 꺼내기 위해 계속 정렬하는 것이 아니라 넣을 때부터 순서를 맞춰 넣어주는 작업을 해야한다.

 

- 일반적인 리스트를 활용해 while 구문 안에서 sort할 경우 O((N^2)logN)이 되므로 너무 느린 속도가 된다. 

 

 해결 전략

 

- heap 자료 구조를 활용해 크기를 정렬하며 문제를 해결한다.

 

- 파이썬의 경우 내장함수로 heap 자료구조를 가지고 있어 활용하기 쉬웠다.

 

-  heap 정렬의 경우 O(NlogN)의 속도로 정렬된다. 하지만 while안에서 계속 sort하는 경우와 달리 한번만 해주면 계속 가장 작은 경우들만 뽑기 때문에 전체 속도는 O(N)에 가깝게 나온다.

 

 코드

 

import heapq
def solution(scoville, K):
    heapq.heapify(scoville)
    cnt = 0
    while True:
        # 가장 작은 요소가 K보다 크면 끝난 것
        notspicy1 = heapq.heappop(scoville)
        if notspicy1 > K:
            return cnt
        # 가장 작은 요소가 K보다 작은 경우
        else :
            # 그런데 한개만 남고 더 섞을 수 없는 경우는 -1을 반환
            if len(scoville) == 0:
                return -1
            # 섞을 소스가 존재
            else :
                # 두번째로 안매운 소스를 뺀다
                notspicy2 = heapq.heappop(scoville)
                # 새로운 소스를 만든다
                newsauce = notspicy1 + (notspicy2*2)
                # 새로운 소스를 넣는다
                heapq.heappush(scoville, newsauce)
                # 횟수 추가
                cnt += 1
 

 

 

 해설

 

- 정렬은 최초에 한번만 해주고 반복문 안에서는 꺼내고 넣는 작업만 하기 때문에 훨씬 속도가 빠르다.

 

- 이렇게 정렬을 반복하지 않고 구조화 한 상태에서 가장 작거나 큰 값만 꺼내 쓸 때에 힙 구조가 유리하다.

 

 새로 학습한 것 & 실수 

 

- 내장함수를 통해 힙 구조를 쉽게 구현할 수 있었다.

 

 

출처 - https://programmers.co.kr/learn/courses/30/lessons/42626