구연지

2.문제이름

3. 수행시간[초(s)]

2823

4. git 주소 URL

https://github.com/Qkite/coding-test-study/blob/main/pccp_practice/%EB%8D%94%EB%A7%B5%EA%B2%8C.py

좋아요 누르기

좋아요 수

: 0

5 more properties

| 코드 작성하기

heapq를 이용한 코드

import heapq

def solution(scoville, K):

    answer = 0
    heapq.heapify(scoville)
		# 리스트를 heap의 형식으로 정렬하게 해줌


		# while문을 걸어줄 때 최솟값이 K보다 작다는 조건에 따라서 반복문을 돌리므로 
		# 제일 처음 최솟값을 구하는 경우는 while문 밖에서 미리 계산해줌
    if(len(scoville) == 1):
        if(heapq.heappop(scoville) < K):
            return -1
        else:
            return answer
    elif (len(scoville) == 0):
        return -1
    else:
        min1 = heapq.heappop(scoville)
        min2 = heapq.heappop(scoville)
        level = min1



    while level < K:
        #queue.put(min1 + 2*min2)
        heapq.heappush(scoville, min1 + 2*min2)

        answer += 1


        if(len(scoville) >=2):
            min1 = heapq.heappop(scoville)
            min2 = heapq.heappop(scoville)
            level = min1
        elif(len(scoville) == 1):
            if (heapq.heappop(scoville) < K):
                return -1
            else:
                return answer

            # return이 섞는 횟수이므로 answer에 1을 더해주지 않음
        else:
            return -1

        # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

    return answer
Python
복사

| 코드 설명하기

(1) 가장 작은 수와 두 번째로 작은 수를 계속 구할 수 있어야 한다 → 자동으로 정렬 되게 하는 경우가 best! → 우선순위 큐 이용하기(heapq, PriorityQueue 모듈 이용)

(2) 새로 계산한 값을 리스트에 새로운 값을 넣을 때 속도가 많이 걸리지 않아야 한다

→ 리스트는 값을 append할 때마다 리스트가 새로 생성되어 O(N)의 시간이 걸리므로 값을 넣고 탐색할 때 속도가 더 빠른(O(logN)) 우선순위 큐를 사용하자

(3) K보다 커질 수 없는 경우 -1을 return하는 조건

(4) 우선순위 큐 내부에 있는 원소의 개수가 2개 보다 작은 경우 pop을 할 수 없음 → 조건에 따라 -1 또는 answer를 return해야 함

•

원소 개수가 2보다 작은 경우 answer 또는 -1을 return하는 조건

    if(len(scoville) == 1):
        if(heapq.heappop(scoville) < K):
            return -1
        else:
            return answer
    elif (len(scoville) == 0):
        return -1
    else:
        min1 = heapq.heappop(scoville)
        min2 = heapq.heappop(scoville)
        level = min1
Python
복사

•

while문을 걸어줄 때 최솟값이 K보다 작다는 조건에 따라서 반복문을 돌리므로 제일 처음 최솟값을 구하는 경우는 while문 밖에서 미리 계산해줌