[프로그래머스 Lv.2] 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=python3

프로그래머스

 

 

❎ 1차 풀이

import heapq

min_heap = []


def solution(scoville, K):
    heapq.heapify(scoville)

    count = 0
    while scoville:
        # pop한 값이 k이상이되면, while 종료

        min_value = heapq.heappop(scoville)
        if min_value >= K:
            return count

        if len(scoville) == 1:
            return count

        # 섞어서 새로운 스코빌 구하기
        sec_min = heapq.heappop(scoville)

        new_scoville = min_value + (sec_min * 2)
        count += 1
        heapq.heappush(scoville, new_scoville)

    return count

문제 흐름에 따라, 코드로 옮겨서 작성해보았다. 

최소힙을 사용하면 구현에 어려움이 없던 문제였다. 하지만 계속 통과하지 못하는 tc가 있었다. 처음엔 heappop에 의해 요소가 1개가 남아있을때를 생각하지 못해서, 그런가보다하고, 원소의 개수가 한개만 남았을땐 어차피 새로운 스코빌 음식을 만들수 없기 때문에 여태 섞은 카운트를 리턴하는 early return 조건을 추가시켜줬다.

 

하지만 , 그래도 오답이 발생해서 다시 문제를 읽어보니.......

결국 K이상의 스코빌 음식을 만들수없다면, -1을 리턴해야한다. 

문제를 좀 똑바로 읽어랏! 저녁먹고 코테 풀려고하니 제일 집중력이 떨어지는것 같다ㅠㅠ

 

 

✅ 정답 풀이

import heapq


def solution(scoville, K):
    heapq.heapify(scoville)

    count = 0
    while len(scoville) >1:
        # 최소값이 k이상이되면, while 종료
        min_value = heapq.heappop(scoville)
        if min_value >= K:
            return count


        # 1,2번째 min값 섞어서 새로운 스코빌 구하기
        sec_min = heapq.heappop(scoville)
        new_scoville = min_value + (sec_min * 2)
        count += 1
        heapq.heappush(scoville, new_scoville)

    # 가장 안매운 스코빌이 K이상인지 확인 (충족되지 않는다면, -1 리턴)
    if scoville[0]>=K:
        return count

    return -1

 

while문으로 카운트를 종료 한 후, 최소값 (scovile[0])이 K 이상인지 여부에 따라 최종값을 리턴해주면된다.

 

 

 

👑 BEST 풀이

import heapq


def solution(scoville, K):
    heapq.heapify(scoville)

    count = 0
    while True:
        first = heapq.heappop(scoville)
        if first >= K:
            break

        if len(scoville)<1:
            return -1
        
        second = heapq.heappop(scoville)
        count += 1
        heapq.heappush(scoville, first + (second * 2))

    return count

로직은 동일하지만, -1을 어떻게 처리할지에 따른 조건문에 약간의 차이가 있다.

❗️K이상의 스코빌을 만족할때 까지, 힙 안의 원소를 계속 pop해가면서 비교하기 때문에

만족하지 않는 -1을 리턴해야하는 경우 scovile 힙의 길이가 0이 될것이다.

 

 

 

✅ JS 풀이

class MinHeap {
  constructor() {
    this.heap = [];
  }

  size() {
    return this.heap.length;
  }
      
    // 값을 넣되, 오름차 순 정렬함
  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;

    while (
      currentIndex > 0 &&
      this.heap[currentIndex] < this.heap[Math.floor((currentIndex - 1) / 2)]
    ) {
      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[Math.floor((currentIndex - 1) / 2)];
      this.heap[Math.floor((currentIndex - 1) / 2)] = temp;
      currentIndex = Math.floor((currentIndex - 1) / 2);
    }
  }

    // 값을 빼되, 오름차 순 정렬 함
  pop() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    let currentIndex = 0;

    while (currentIndex * 2 + 1 < this.heap.length) {
      let minChildIndex = currentIndex * 2 + 2 < this.heap.length && this.heap[currentIndex * 2 + 2] < this.heap[currentIndex * 2 + 1] ? currentIndex * 2 + 2 : currentIndex * 2 + 1;

      if (this.heap[currentIndex] < this.heap[minChildIndex]) {
        break;
      }

      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[minChildIndex];
      this.heap[minChildIndex] = temp;
      currentIndex = minChildIndex;
    }

    return minValue;
  }

  peek() {
    return this.heap[0];
  }
}
function solution(scoville, K) {
    var answer = 0;
    
    const minHeap=new MinHeap();
    
    //minHeap 생성
    for(const sco of scoville){
        minHeap.push(sco);
    }
    
    while(minHeap.size()>=2 && minHeap.peek()<K){
        //1,2번째 음식 스코필 구해서 새로운 스코빌 음식 만들기
        const first=minHeap.pop();
        const second=minHeap.pop();
        const mixedFood=first+(second*2);
        
        //새로운 스코필 음식 heap에 넣기
        minHeap.push(mixedFood);
        answer+=1;
    }
    
    return minHeap.peek()>=K ? answer : -1
    
    
}

 

자바스크립트는 heap을 클래스로 구현해야하기 때문에, 체감상 훨씬 어렵고 복잡해진다 😂