[Problem Solving] 프로그래머스 42626 더 맵게

더 맵게 문제 풀이에 대한 글입니다. 문제 설명은 다음의 링크를 확인해주시기 바랍니다. 문제 설명

코딩테스트 연습 - 더 맵게

더 맵게 문제는 모든 음식의 스코빌 지수를 K 이상으로 만드는데 몇 번의 계산을 했는지를 구하는 문제입니다. 여기서 계산은 다음과 같이 진행됩니다.

 

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

위의 계산을 수행하기 위해서는 주어진 스코빌 배열에서 가장 작은 스코빌 지수, 두 번째로 작은 스코빌 지수를 계산이 완료될 때까지 가져와야 합니다. 계산을 다시 시작할 때마다 배열을 정렬시켜 배열[0], 배열[1]의 값을 가져오는 방법을 선택할 수도 있지만 이 방법은 정렬의 시간 복잡도 O(nlogn) 최악의 경우 n번의 반복이 합쳐 저 O(n^2 logn)의 시간 복잡도가 나올 수 있습니다. 따라서 답은 구할 수 있겠지만 효율성 테스트에서 시간 초과가 나옵니다.

 

이 문제를 해결하기 위해서는 힙을 사용해야 합니다. 힙의 성질은 다음과 같습니다. 기준은 최소힙입니다.

• 부모 노드의 값이 자식 노드의 값보다 항상 작다.
• 완전 이진트리의 성질을 만족합니다.

파이썬에서 제공하는 heapq 모듈의 주요 기능 시간 복잡도는 다음과 같습니다.

• 주어진 배열을 힙으로 변환하는 heapify()는 O(n)
• 힙에 원소를 추가하는 heappush()는 O(logn)
• 힙의 원소를 제거하는 heappop()은 O(logn)

따라서 힙을 사용하면 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다.

 

다음은 힙을 사용하여 문제를 해결하는 순서입니다.

1. scoville 배열을 힙으로 변환한다.
2. 가장 작은 값이 K보다 큰지 확인한다.
3. 2번을 만족하면 answer를 반환한다.
4. scoville 배열의 길이가 2보다 큰지 확인한다.
5. 4번을 만족하면 정답이 존재하지 않으므로 -1을 반환한다.
6. 첫 번째로 작은 scoville과 두 번째로 작은 scoville을 힙의 성질을 이용하여 꺼낸다.
7. 문제에서 제시한 식에 맞게 스코빌을 계산한 원소를 scoville에 힙의 성질에 맞게 넣어준다.
8. 2를 반복한다.

위의 해결 순서에서 2번과 4번은 정답과 실패를 판단하는 조건입니다.

2번의 경우 가장 작은 값이 K보다 크다면 scoville 배열의 다른 모든 값이 K보다 크다고 할 수 있기 때문에 answer를 반환합니다. 4번의 경우 배열의 길이가 2보다 작다면 더 이상 새로운 스코빌을 계산할 수 없기 때문에 정답이 없다는 의미로 -1을 반환합니다.

 

해결 순서를 바탕으로 코드를 작성하면 다음과 같습니다.

 

import heapq

def calcShakeScoville(first, second):
    return first + (second * 2)

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

  while scoville[0] < K:
    if len(scoville) < 2:
      return -1
    else:
      first = heapq.heappop(scoville)
      second = heapq.heappop(scoville)
      heapq.heappush(scoville, calcShakeScoville(first, second))
      answer += 1
  return answer

 

배열에서 힙의 성질은 정렬시키는 것으로도 만족시킬 수 있습니다. 따라서 heapq.heapify(scoville) 부분을 scoville.sort()로 변환하여도 문제를 해결할 수 있습니다. 힙을 사용해야 한다는 것만 안다면 어렵지 않게 문제를 해결할 수 있습니다.