[프로그래머스] LEVEL2 더 맵게 파이썬

[프로그래머스] LEVEL2 더 맵게

---

✔️문제

문제 설명

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

---

✔️풀이

❌실패한 코드

6,7,10,13,19번을 실패하고, 효율성 시간 초과한 코드

def solution(scoville, K):
    answer = 0
    scoville = sorted([x for x in scoville if x<K])
    if not len(scoville):
        return answer
    while len(scoville)>1:
        answer += 1
        scoville = sorted([scoville[0] + scoville[1]*2] + scoville[2:])
        if scoville[0]>=K:
            return answer
        scoville = sorted([x for x in scoville if x<K])
    else:
        return -1

1. 스코빌 지수가 이미 K이상이라면 바로 0을 리턴해준다.
2. 스코빌 지수가 K이상인 숫자는 제외하고 오름차순으로 정렬해준다.
3. while문을 돌면서 음식을 섞고 정렬해준다.
4. 제일 작은 음식의 스코빌 지수가 K이상이면 answer을 리터해준다.
5. 남은 음식이 1개인데 스코빌 지수가 K보다 작다면 K이상으로 만들 수 없는 경우이므로 -1을 리턴한다.

배열의 길이가 최대 1,000,000이므로 효율성 테스트를 통과하지 못했다.

✅통과한 코드

import heapq

def solution(scoville, K):
    answer = 0
    heap = []
    scoville = [x for x in scoville if x<K]
    if not len(scoville):
        return 0
    for i in scoville :
        heapq.heappush(heap, i)
        
    while heap[0]<K:
        answer += 1
        try:
            heapq.heappush(heap, heapq.heappop(heap) + heapq.heappop(heap)*2)
        except:
            return -1
    
    return answer

heapq를 사용해서 해결했다.
heapq는 일반적은 리스트와 달리 push와 pop을 할 때마다 자동으로 정렬을 해준다. 따라서 크기가 큰 배열을 정렬할 때 효율성이 좋다.

위의 코드에서 정렬부분을 제외하고 heapq를 이용해서 코드를 작성했다.

👍오늘의 배운 점

💡heapq

heapq 모듈은 이진 트리 기반의 최소 힙(min heap) 자료구조를 제공한다.
최소 힙을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은 값은 언제나 인덱스 0인 이진 트리의 루트에 위치한다.

heapq 모듈은 내장 모듈로 임포트 후 내장 함수를 사용할 수 있다.

from heapq import heappush, heappop

heapq 모듈은 파이썬의 보통 리스트를 최소 힙처럼 다룰 수 있도록 해준다. 빈 리스트를 생성하고 heapq 모듈을 통해서 원소를 추가하거나 삭제한다.

heap = []

• 힙에 원소 추가

heapq 모듈의 heappush() 함수를 이용하여 힙에 원소를 추가할 수 있다.

from heapq import heappush

heappush(heap, 4)
heappush(heap, 3)
heappush(heap, 2)
heappush(heap, 1)
print(heap)

[1, 2, 3, 4]

• 힙에서 원소 삭제

heapq 모듈의 heappop() 함수를 이용하여 힙에서 원소를 삭제할 수 있다.

from heapq import heappop

print(heappop(heap))
print(heap)

1
[2, 3, 4]

가장 작은 1이 삭제되고 2가 인덱스 0에 위치하게 된다.