[4코1파] #48. 더 맵게

gunny·2023년 2월 20일

4코1파 heap 코딩테스트 코딩테스트 heap 코딩테스트 python 프로그래머스 더 맵게 프로그래머스 더 맵게 python

코딩테스트

목록 보기

48/530

[4코1파] 4명의 안드로이드 개발자와 1명의 파이썬 개발자의 코딩 테스트 서막 : 4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원

START :

[3코1파] 2023.01.04~ (48일차)
[4코1파] 2023.01.13~ (39일차)

Today :

2023.02.20 [48일차]

프로그래머스 LV2
더 맵게
https://school.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 합니다.

입출력 예

입출력 예 설명

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

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.
※ 공지 - 2022년 12월 23일 테스트 케이스가 추가되었습니다. 기존에 제출한 코드가 통과하지 못할 수도 있습니다.

문제 풀이 방법

일단 문제 옆에 나와있는게 'heap' 이어서,
heap을 활용해서 풀어야 하는 문제이구나 싶었음
처음에는 queue를 활용하려고 하다가 heap을 이용한 문제는 한번도 풀어본적이 없어서 heap으로 구현 해보기로 함

일단 heap 에 대해서 좀 찾아봤고
python에서의 heap은 heapq로 import를 하고
push는 heapq.heappush, pop은 heapq.heappop 입
힙합~!
여기서 알게된건 heap 에서의 heapq.heappop은 자동으로
최솟값을 return 해준다는거다~ pop 기능을 원하지 않으며
인덱스 [0] 등으로 찾아나설 수 있음..

정석적으로 문제에서 요구하는 최솟값 두개를 뽑아서
비교해서 스코빌 지수 구하는 구현 완료

사실 마지막 효율성 5에서 계속 ... 거려서 긴장 탐

증빙

내 코드

import heapq

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

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

    return answer

다른 사람 풀이
애초부터 주어진 range에 대해 for문을 돌리고,
try except 문으로 풀어버린 구현