[프로그래머스] 더 맵게 (Level 2) (파이썬 python)

 

 

문제 링크

 

 

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

코딩테스트 연습 - 더 맵게

 

 

문제

 

 

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다.

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을

아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

 

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

 

 

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때,

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

최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

 

제한 사항

 

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

입출력 예

 

scoville / K / return

[1, 2, 3, 9, 10, 12]

7

2

 

 

입출력 예 설명

 

스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

 

스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]

 

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

 

 

문제 풀이

 

 

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while len(scoville) >= 2:
        # 가장 작은 수
        min1 = heapq.heappop(scoville)
        if min1 >= K:
            return answer
        else:
            # 두번째로 작은 수
            min2 = heapq.heappop(scoville)
            heapq.heappush(scoville, min1 + min2 * 2)
            answer += 1
    if scoville[0] > K:
        return answer
    else:
        return -1

 

 

파이썬은 참 간결하고 쉽게 푸는 방법이 많은 것 같다

힙큐 모듈을 처음 사용해봤는데 편리한 것 같다 포스팅을 통해 정리해놔야겠음!

 

일단 제공된 scoville 리스트를 heapify 메소드를 이용해 힙 자료형으로 변환한다.

연산을 위해 필요한 scoville의 원소의 개수는 최소 2개이므로 scoville의 길이가 2 이상일 때를 조건으로 걸어둔다.

heappop을 통해 가장 작은 수를 빼내었을 때 해당 숫자가 K보다 클 경우 그대로 answer을 리턴해준다.

그렇지 못할 경우 가장 작은 두 숫자를 연산해주고 heapq에 append해주어야 하므로 해당 연산식을 추가해주었다.

처음에는 여기까지 작성해서 제출했는데, 하나의 테스트에서 실패하였다.

연산이 끝난 후 원소가 1개가 남았거나 0개가 남은 경우를 고려하지 못한 것이 이유였다.

1개가 남았을 때에도 이 원소가 K 이상이 되면 조건을 만족한 것이 된다.

while문 바깥에서 이것을 검사하는 식을 써주면 코드가 비로소 완성된다!