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

[프로그래머스] 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626

문제 설명

· 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 섞음

· 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

· 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞음

· 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수 반환

· 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1

최대길이가 매우 크므로 정렬을 하지 않고 작은 음식 두개를 찾아낼 방법을 찾아야 하는 문제

접근 방법

· 작은 음식 두개를 찾기위해 섞을때마다 정렬할경우 최소 O(N^2logN)의 복잡도를 가지므로 사실상 불가

· Heapq 구조를 이용하면 push엔 조금 시간이 걸리지만 정렬을 하지 않아도 크기 순서를 유지 가능

· 최소 음식의 스코빌 지수가 K 미만이지만 섞을 음식이 없을 경우 -1 반환

· 최소 음식의 스코빌 지수가 K 이상일 경우 count 반환

알고리즘 설계 및 구현

import heapq

def solution(scoville, K):
    count = 0
    heapq.heapify(scoville)
    
    min = heapq.heappop(scoville)
    
    while min < K:
        if len(scoville) < 1:
            return -1
        else:
            count +=1 
            heapq.heappush(scoville, min + heapq.heappop(scoville)*2)
            min = heapq.heappop(scoville)
        
    return count

결과

최적화 및 개선 사항

· 이론상 deque를 통해 섞기 전 배열과 섞은 후 배열을 두개 만든 후 앞부분 원소만 비교하면 훨씬 빠를 수 있다.