[프로그래머스] 더 맵게

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 합니다.

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

입출력 예 설명

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

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

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

코드

def solution(scoville, K):
    answer = 0
    scoville.sort(reverse=True)

    while scoville[-1] < K:
        min = scoville.pop()
        scoville[-1] = min + scoville[-1] * 2
        scoville.sort(reverse=True)
        answer+=1

    return answer

파이썬 힙 강의 듣고 힙만들다가 그냥 해봤다. 런타임에러 몇 개를 냈고, 성능테스트는 모두 시간초과가 나왔다.
모든 음식을 고려해도 K보다 작을 때 -1을 리턴하라는 조건 때문에 런타임 에러가 나온 것 같고, while안에 계속 sort가 있어서 시간초과가 나온 것 같다.

def solution(scoville, K):
  answer = 0
  heap = minHeap(scoville.pop());
  for i in scoville:
      heap.insert(i)
  while heap.arr[1] < K and len(heap.arr) > 2:
      heap.insert(heap.pop() + heap.pop() * 2)
      answer+=1  

  if len(heap.arr) <= 2:
      return -1
  else:
      return answer

class minHeap:
  def __init__(self, data):
      self.arr = list()
      self.arr.append(None)
      self.arr.append(data)

  def move_up(self, idx):
      if idx <= 1:
          return False
      pidx = idx // 2
      if self.arr[idx] < self.arr[pidx]:
          return True
      else:
          return False

  def insert(self, data):
      if len(self.arr) == 0:
          self.arr.append(None)
          self.arr.append(data)
          return True

      self.arr.append(data)
      idx = len(self.arr) - 1
      while(self.move_up(idx)):
          pidx = idx // 2
          self.arr[idx], self.arr[pidx] = self.arr[pidx], self.arr[idx]
          idx = pidx

      return True

  def move_down(self, idx):
      lidx = idx * 2
      ridx = idx * 2 + 1

      if lidx >= len(self.arr):
          return False

      elif ridx >= len(self.arr):
          if self.arr[idx] > self.arr[lidx]:
              return True
          else:
              return False
      else:
          if self.arr[lidx] < self.arr[ridx]:
              if self.arr[idx] > self.arr[lidx]:
                  return True
              else:
                  return False
          else:
              if self.arr[idx] > self.arr[ridx]:
                  return True
              else:
                  return False


  def pop(self):
      if len(self.arr) <= 1:
          return None

      min = self.arr[1]
      self.arr[1] = self.arr[-1]
      self.arr.pop()
      idx = 1

      while self.move_down(idx):
          lidx = idx * 2
          ridx = idx * 2 + 1

          if ridx >= len(self.arr):
              if self.arr[idx] > self.arr[lidx]:
                  self.arr[idx], self.arr[lidx] = self.arr[lidx], self.arr[idx]
          else:
              if self.arr[lidx] < self.arr[ridx]:
                  if self.arr[idx] > self.arr[lidx]:
                      self.arr[idx], self.arr[lidx] = self.arr[lidx], self.arr[idx]
              else:
                  if self.arr[ridx] < self.arr[idx]:
                      self.arr[idx], self.arr[ridx] = self.arr[ridx], self.arr[idx]

      return min

힙을 만들어서 풀었다. 시간복잡도는 줄어든 것 같은데 정확도가 엉망이다.
질문하기에서 테스트케이스를 하나 주워서 돌려봤는데 스코빌지수의 최소값을 뽑아내는 과정에서 맨 밑에 있는 값이 힙의 제일 위로 가는데 거기서 잘 안 돌아가는 것 같다.
move_down 메서드에서 자식노드와 위치를 교체하고나서 idx도 바꿔줬어야했는데 그걸 안 해줘서 문제가 발생했던 것이었다.

def solution(scoville, K):
    answer = 0

    heap = minHeap(scoville.pop());

    for i in scoville:
        heap.insert(i)

    while heap.arr[1] < K and len(heap.arr) > 2:
        min1 = heap.pop()
        min2 = heap.pop()
        heap.insert(min1 + min2 * 2)
        answer+=1

    if len(heap.arr) <= 2:
        return -1
    else:
        return answer


class minHeap:
    def __init__(self, data):
        self.arr = list()
        self.arr.append(None)
        self.arr.append(data)

    def move_up(self, idx):
        if idx <= 1:
            return False
        pidx = idx // 2
        if self.arr[idx] < self.arr[pidx]:
            return True
        else:
            return False

    def insert(self, data):
        if len(self.arr) == 0:
            self.arr.append(None)
            self.arr.append(data)
            return True

        self.arr.append(data)
        idx = len(self.arr) - 1
        while(self.move_up(idx)):
            pidx = idx // 2
            self.arr[idx], self.arr[pidx] = self.arr[pidx], self.arr[idx]
            idx = pidx

        return True

    def move_down(self, idx):
        lidx = idx * 2
        ridx = idx * 2 + 1

        if lidx >= len(self.arr):
            return False

        elif ridx >= len(self.arr):
            if self.arr[idx] > self.arr[lidx]:
                return True
            else:
                return False
        else:
            if self.arr[lidx] < self.arr[ridx]:
                if self.arr[idx] > self.arr[lidx]:
                    return True
                else:
                    return False
            else:
                if self.arr[idx] > self.arr[ridx]:
                    return True
                else:
                    return False


    def pop(self):
        if len(self.arr) <= 1:
            return None

        min = self.arr[1]
        self.arr[1] = self.arr[-1]
        self.arr.pop()
        idx = 1

        while self.move_down(idx):
            lidx = idx * 2
            ridx = idx * 2 + 1

            if ridx >= len(self.arr):
                if self.arr[idx] > self.arr[lidx]:
                    self.arr[idx], self.arr[lidx] = self.arr[lidx], self.arr[idx]
                    idx = lidx
            else:
                if self.arr[lidx] < self.arr[ridx]:
                    if self.arr[idx] > self.arr[lidx]:
                        self.arr[idx], self.arr[lidx] = self.arr[lidx], self.arr[idx]
                        idx = lidx
                else:
                    if self.arr[ridx] < self.arr[idx]:
                        self.arr[idx], self.arr[ridx] = self.arr[ridx], self.arr[idx]
                        idx = ridx

        return min

그런데도 테스트케이스 3개 정도 틀렸고 이제는 성능 테스트를 전부 통과 못하고 있다.

def solution(scoville, K):
    answer = 0

    heap = minHeap(scoville.pop());
    for i in scoville:
        heap.insert(i)

    while heap.arr[1] < K and len(heap.arr) > 2:
        min1 = heap.pop()
        min2 = heap.pop()
        heap.insert(min1 + min2 * 2)
        answer+=1

    if len(heap.arr) <= 2 and heap.arr[1] < K:
        return -1
    else:
        return answer


class minHeap:
    def __init__(self, data):
        self.arr = list()
        self.arr.append(None)
        self.arr.append(data)

    def move_up(self, idx):
        if idx <= 1:
            return False
        pidx = idx // 2
        if self.arr[idx] < self.arr[pidx]:
            return True
        else:
            return False

    def insert(self, data):
        if len(self.arr) == 0:
            self.arr.append(None)
            self.arr.append(data)
            return True

        self.arr.append(data)
        idx = len(self.arr) - 1
        while(self.move_up(idx)):
            pidx = idx // 2
            self.arr[idx], self.arr[pidx] = self.arr[pidx], self.arr[idx]
            idx = pidx

        return True

    def move_down(self, idx):
        lidx = idx * 2
        ridx = idx * 2 + 1

        if lidx >= len(self.arr):
            return False

        elif ridx >= len(self.arr):
            if self.arr[idx] > self.arr[lidx]:
                return True
            else:
                return False
        else:
            if self.arr[lidx] < self.arr[ridx]:
                if self.arr[idx] > self.arr[lidx]:
                    return True
                else:
                    return False
            else:
                if self.arr[idx] > self.arr[ridx]:
                    return True
                else:
                    return False


    def pop(self):
        if len(self.arr) <= 1:
            return None

        min = self.arr[1]
        self.arr[1] = self.arr[-1]
        self.arr.pop()
        idx = 1

        while self.move_down(idx):
            lidx = idx * 2
            ridx = idx * 2 + 1

            if ridx >= len(self.arr):
                if self.arr[idx] > self.arr[lidx]:
                    self.arr[idx], self.arr[lidx] = self.arr[lidx], self.arr[idx]
                    idx = lidx
            else:
                if self.arr[lidx] < self.arr[ridx]:
                    if self.arr[idx] > self.arr[lidx]:
                        self.arr[idx], self.arr[lidx] = self.arr[lidx], self.arr[idx]
                        idx = lidx
                else:
                    if self.arr[ridx] < self.arr[idx]:
                        self.arr[idx], self.arr[ridx] = self.arr[ridx], self.arr[idx]
                        idx = ridx

        return min
        

질문하기를 참고하니까 스코빌 배열의 전부를 써서 하나가 남았을 때 그리고 그 값이 K보다 클 때는 -1를 반환하면 안 되는데 -1를 반환하고 있어서 조건을 하나 추가해줬다. 그렇지만 성능테스트를 통과 못한다.
질문하기를 또 참고했는데 직접만든 힙은 통과 못하고 파이썬에 heapq 모듈이 있는데 그것을 사용해야한다고 한다.

from heapq import heappush, heappop

def solution(scoville, K):
    answer = 0

    heap = []

    for i in scoville:
        heappush(heap, i)



    while len(heap) > 1 and heap[0] < K:
        min1 = heappop(heap)
        min2 = heappop(heap)
        heappush(heap, min1 + min2 * 2)
        answer+=1

    if len(heap) <= 1 and heap[0] < K:
        return -1
    else:
        return answer

heapq만 호출했고 나머지 solution 함수에서의 모양은 그대로 사용했다. heapq쓰니까 성능테스트도 통과했다. 내가 만든 heap은 안 좋은 heap이었나보다.