프로그래머스 - 더 맵게

[프로그래머스] 기능개발

Link

문제

매운 것을 좋아하는 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

풀이

개인적으로 프로그래머스 문제들의 설명을 보면 최대한 일상생활이나 특정 주제를 가지고 문제의 본질을 가려놓는 경향이 있는 것 같다.

처음에는 왜이렇게 되어있나에 대한 불만이 있었는데 다시 생각해보면 결국 우리가 하고자하는 일이 일상생활의 불편함을 효율적으로 줄여보고자 하는 것이고, 결국 그러려면 일상생활의 소재와 알고리즘의 입력, 출력, 과정들을 연결해야하는 것이기 때문에 이런 연습을 하는것도 좋다고 생각하게 되었다.

아무튼 이번 문제는 음식을 섞어 모든 음식의 스코빌 지수가 K이상이 되도록 만드는데 섞어야하는 최소 횟수를 Return하는 문제이다. (scovile안의 모든 수가 k 이상이 되어야 한다.)

• scoville 변수에는 각 음식의 스코빌 지수가 1D 배열 형태로 오름차순으로 정렬되어 들어있다. (길이는 2 이상으로 하나만 입력으로 주어지는 경우는 없다.)

• k는 0 이상 십억 이하의 수이고, 모든 음식을 섞어도 k이상으로 만들 수 없을 때 -1을 return해야한다.
• scoville안의 제일 작은 수가 k 이상이면 모든 음식의 스코빌 지수가 k이상이다.
• 작은 스코빌 지수를 가진 것들 끼리 먼저 섞다보면 어느 순간 모든 음식의 스코빌 지수가 k이상이 된다.
  • 하지만 꼭 이럴 경우 음식을 섞는 횟수가 최소가 되는지 물어보면 확신을 못하겠다.

정리하면 결국 작은 스코빌 지수를 가진 것들 끼리 섞을 거니까 scovile은 항상 정렬되어있어야한다.

scoville[0]이 k보다 크거나 같으면 그때의 반복 횟수를 return해야한다. (언제든지)

모든 음식을 전부 섞었는데도 (=scoville 배열의 길이가 1인데도 = scoville 배열의 길이가 2보다 작은데도) k보다 작다면 그때는 -1을 return해야한다.

Flow

1. heap = heapq.heapify(scovile)
2. answer = 0
3. 첫번째와 두번째 수를 pop한다. 이때 첫번째나 두번째 수가 k보다 크면 answer를 return
4. 아니라면 새로운 스코빌 지수 new_scovile을 생성
5. 이걸 heap에 push
6. answer += 1
7. heap의 길이가 1보다 클때까지만 반복
8. return -1

import heapq
def solution(scoville, K):
    answer = 0
    
    heapq.heapify(scoville)

    while len(scoville) > 1:
        v1 = heapq.heappop(scoville)
        v2 = heapq.heappop(scoville)
        if v1 >= K:
            return answer
        new_v = v1 + (v2 * 2)
        heapq.heappush(scoville, new_v)
        answer += 1
        
    if scoville[0] >= K:
        return answer
    else:
        return -1