[프로그래머스] 더 맵게

1. 문제

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

코딩테스트 연습 - 더 맵게

2. 내가 생각했던 첫번째 풀이과정

 

1) 가장 맵지 않은 음식과 두번째로 맵지 않은 음식을 골라야하니 일단 배열을 정렬한다

2) 가장 맵지 않은 음식과 두번째로 맵지 않은 음식을 계산을 한다

3) 계산을 한 이후에는 첫번째 요소를 pop을 해주면서, 계산한 값을 첫번째 요소에 넣고, count를 올린다

 

이럴 경우, 테스트케이스는 맞았으나 시간초과가 되어서 heap을 생각하게 되었다.

 

3. 나의 첫번째 풀이

def solution(scoville, K):
    answer = 0
    for i in range(len(scoville)):
        sorted(scoville)
        if scoville[0] >= K:
            print(answer)
            return answer
        else:
            temp = scoville[0] + scoville[1] * 2
            scoville.pop(0)
            scoville[0] = temp
            answer += 1

 

4. 나의 두번째 풀이

import heapq

def solution(scoville, K):
    count = 0
    heapq.heapify(scoville) # 값이 들어있는 리스트를 힙으로 변환
    while scoville[0] < K:
        if len(scoville) > 1:
            heapq.heappush(scoville, heapq.heappop(scoville) + (heapq.heappop(scoville) * 2))
            count += 1
        else:
            return -1
    print(count)
    return count

solution(scoville, K)

heapq는 우선순위 큐 알고리즘이다.

heapq는 리스트와 다르게, 가지고 있는 요소를 push, pop을 할 때마다 자동으로 정렬을 해준다.

 

우선 값이 들어있는 리스트를 heapq.heapify( )를 사용하여 값이 들어있는 리스트를 힙으로 변환해준다

배열의 가장 작은 요소가 K보다 작을 경우 루프를 돌게 해준다.

이 때, 리스트의 길이가 1보다 작을 경우, heappop( )을 통해 반환된 가장 작은 값과 반환된 두번째 값을 통해 계산을 하여 다시 리스트에 넣어주고, count를 올린다.

만약 리스트 길이가 0이라면 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우임으로 -1을 return 합니다.

 

5. 새로 알게된 점

1) heapq 자료구조

 

heapq.heappush(heap, item)

- 힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.

heapq.heappop(heap)

- 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환합니다. 힙이 비어 있으면, IndexError가 발생합니다. 팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용하십시오.

heapq.heappushpop(heap, item)

- 힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 팝하고 반환합니다. 결합한 액션은 heappush()한 다음 heappop()을 별도로 호출하는 것보다 더 효율적으로 실행합니다.

heapq.heapify(x)

- 리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.

heapq.heapreplace(heap, item)

- heap에서 가장 작은 항목을 팝하고 반환하며, 새로운 item도 푸시합니다. 힙 크기는 변경되지 않습니다. 힙이 비어 있으면, IndexError가 발생합니다.

 

• 참고

- heapq 공식 문서 : python.flowdas.com/library/heapq.html

heapq --- 힙 큐 알고리즘 — 파이썬 설명서 주석판