[Python] 더 맵게

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

프로그래머스

 

접근법

• K 미만의 값을 반복해서 찾아야 함.
  -> 첫번째 값으로 최소값을 보장하는 heapq 모듈을 사용하여 우선순위큐를 활용.
• 반복해서 0번째 index의 값을 뽑아서 K 보다 작은지 확인을 한 후 K보다 작다면 새 스코빌 지수를 작성하여 heap에 push함.
• 이를 0번째 index의 값이 K보다 크거나, 힙의 길이가 2초과일때까지만 반복함. 

 

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        if len(scoville) < 2:
            return -1
        
        first_sc = heapq.heappop(scoville)
        second_sc = heapq.heappop(scoville)
        
        new_sc = first_sc + second_sc * 2
        heapq.heappush(scoville, new_sc)
        answer += 1
            
    return answer

---

처음 생각했던 알고리즘의 문제점(틀린이유)

리스트를 정렬한 후 순서대로 pop을 해서 K보다 작은지 확인한 후 새 스코빌 지수를 append하고자 했음.

pop을 활용하기 때문에 시간복잡도를 고려하여 내림차순으로 정렬한 후 -1번째부터 pop을 하고자함.

다만 이 방법을 활용한다면 새 스코빌 지수가 append 된 후 순서를 보장할 수 없기 때문에 에러가 발생했다.

def solution(scoville, K):
    answer = 0
    
    scoville.sort(reverse = True)
    while scoville[-1] < K:
        if len(scoville) < 2:
            return -1
        
        first_sc = scoville.pop()
        second_sc = scoville.pop()
        
        new_sc = first_sc + second_sc * 2
        scoville.append(new_sc)
        answer += 1
            
    return answer

 

 

사용된 알고리즘

힙(heapq)