[프로그래머스] 더 맵게 (LV2 - JavaScript)

프로그래머스

1. 문제

매운 것을 좋아하는 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. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

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

 

2. 오답

function solution(scoville, K) {
    let answer = 0;
    // dfs
    const dfs = (arr) => {
        answer++;
        // 배열을 [섞은 음식의 스코빌 지수, ...나머지 음식]으로 초기화
        arr = [arr[0] + (arr[1] * 2), ...arr.slice(2)];
        // 섞는 연산이 가능하고 기준 K를 넘지 못한 음식이 남아있으면 dfs 재귀 호출
        if (arr.length > 1 && arr.filter(val => val < K).length > 0) return dfs(arr.sort((a,b) => a-b));
        // 섞는 연산이 불가능하면 기준 K를 넘긴 음식의 배열을 반환
        return arr.filter(val => val >= K);
    }
    
    // 모든 음식이 기준 K를 넘었다면 dfs 탐색하지 않고 0 리턴
    if (scoville.filter(val => val < K).length < 1) return answer;
    // dfs에서 반환된 기준 K를 넘긴 음식의 배열 요소가 있으면
    // 섞은 횟수 answer를 반환, 없으면 -1을 반환
    return dfs(scoville.sort((a,b) => a-b)).length > 0 ? answer : -1;
}

dfs로 풀었더니 효율성 테스트에서 메모리 초과 오류가 발생한다.

어떤 방법으로 풀어야할지 감이 안 와서 다른 사람의 풀이를 찾아봐야겠다😓😓

 

3. 다른 사람 풀이

풀이 전략

• Heap 구조를 활용

// MinHeap 클래스를 정의하는 코드입니다. 이 클래스는 최소 힙을 구현합니다.
class MinHeap {
  // constructor는 클래스의 생성자 메서드로, 힙을 저장할 빈 배열 heap을 초기화합니다.
  constructor() {
    this.heap = [];
  }

  // getParentIndex 메서드는 주어진 인덱스의 부모 노드 인덱스를 계산하여 반환합니다.
  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
    // 부모 노드의 인덱스는 (index - 1) / 2의 내림 값입니다.
  }

  // getLeftChildIndex 메서드는 주어진 인덱스의 왼쪽 자식 노드 인덱스를 계산하여 반환합니다.
  getLeftChildIndex(index) {
    return 2 * index + 1;
    // 왼쪽 자식 노드의 인덱스는 2 * index + 1입니다.
  }

  // getRightChildIndex 메서드는 주어진 인덱스의 오른쪽 자식 노드 인덱스를 계산하여 반환합니다.
  getRightChildIndex(index) {
    return 2 * index + 2;
    // 오른쪽 자식 노드의 인덱스는 2 * index + 2입니다.
  }

  // swap 메서드는 힙의 두 노드의 값을 교환합니다.
  swap(index1, index2) {
    const temp = this.heap[index1];
    this.heap[index1] = this.heap[index2];
    this.heap[index2] = temp;
    // 임시 변수 temp를 사용하여 index1의 값을 저장합니다.
    // 그리고 index1에 index2의 값을 할당한 후 index2에 temp의 값을 할당합니다.
  }

  // push 메서드는 새로운 요소를 힙에 삽입합니다.
  push(value) {
    this.heap.push(value);

    // currentIndex는 삽입된 요소의 인덱스이고, parentIndex는 부모 노드의 인덱스입니다.
    let currentIndex = this.heap.length - 1;
    let parentIndex = this.getParentIndex(currentIndex);

    // 삽입된 요소가 루트 노드가 아니고, 부모 노드의 값이 삽입된 요소의 값보다 크다면 교환합니다.
    // 교환 후에는 currentIndex를 parentIndex로 업데이트하고, 다시 parentIndex를 구합니다.
    while (
      currentIndex > 0 &&
      this.heap[parentIndex] > this.heap[currentIndex]
    ) {
      this.swap(currentIndex, parentIndex);
      currentIndex = parentIndex;
      parentIndex = this.getParentIndex(currentIndex);
    }
    // 이 과정을 반복하여 힙의 속성을 유지합니다.
  }

  // pop 메서드는 힙에서 가장 작은 요소(루트 노드)를 꺼내고 제거합니다.
  pop() {
    // 힙이 비어있다면 null을 반환합니다.
    if (this.isEmpty()) return null;

    // 힙에 요소가 하나밖에 없다면 해당 요소를 제거하고 반환합니다.
    if (this.heap.length === 1) return this.heap.pop();

    // 루트 노드의 값을 root 변수에 저장하고, 힙의 마지막 요소를 루트 노드로 이동시킵니다.
    const root = this.heap[0];
    this.heap[0] = this.heap.pop();

    // currentIndex는 현재 노드의 인덱스이고, leftChildIndex와 rightChildIndex는 각각 왼쪽과 오른쪽 자식 노드의 인덱스입니다.
    let currentIndex = 0;
    let leftChildIndex = this.getLeftChildIndex(currentIndex);
    let rightChildIndex = this.getRightChildIndex(currentIndex);

    // 현재 노드의 값이 왼쪽 자식이나 오른쪽 자식보다 크다면 교환이 필요합니다.
    while (
      (leftChildIndex < this.heap.length &&
        this.heap[currentIndex] > this.heap[leftChildIndex]) ||
      (rightChildIndex < this.heap.length &&
        this.heap[currentIndex] > this.heap[rightChildIndex])
    ) {
      // 왼쪽 자식과 오른쪽 자식 중 더 작은 값을 가진 노드와 교환합니다.
      const smallerChildIndex =
        rightChildIndex >= this.heap.length ||
        this.heap[leftChildIndex] < this.heap[rightChildIndex]
          ? leftChildIndex
          : rightChildIndex;
      this.swap(currentIndex, smallerChildIndex);

      // 교환 후에는 currentIndex를 교환한 자식 노드의 인덱스로 업데이트하고, 다시 leftChildIndex와 rightChildIndex를 구합니다.
      currentIndex = smallerChildIndex;
      leftChildIndex = this.getLeftChildIndex(currentIndex);
      rightChildIndex = this.getRightChildIndex(currentIndex);

      // 이 과정을 반복하여 힙의 속성을 유지합니다.
    }

    // 마지막으로 제거된 루트 노드의 값 root를 반환합니다.
    return root;
  }

  // isEmpty 메서드는 힙이 비어있는지 확인합니다.
  isEmpty() {
    // 힙의 길이가 0이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
    return this.heap.length === 0;
  }
}

// solution 함수는 주어진 스코빌 지수 배열 scoville과 목표 스코빌 지수 K를 받습니다.
// 그리고 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 반환합니다.
function solution(scoville, K) {
  // 먼저 MinHeap 클래스의 인스턴스 minHeap을 생성합니다.
  const minHeap = new MinHeap();

  // for 반복문을 사용하여 scoville 배열의 모든 요소를 minHeap에 삽입합니다.
  for (let i = 0; i < scoville.length; i++) {
    minHeap.push(scoville[i]);
  }

  // count 변수를 초기화하여 섞은 횟수를 저장합니다.
  let count = 0;

  // while 반복문을 사용하여 minHeap의 루트 노드(가장 작은 스코빌 지수)가 K 미만인 동안 반복합니다.
  while (minHeap.heap[0] < K) {
    // 만약 minHeap에 요소가 1개밖에 없다?
    // 그러면 합할 개수 부족으로 모든 음식을 K 이상으로 만들 수 없으므로 -1을 반환합니다.
    if (minHeap.heap.length === 1) return -1;

    // minHeap에서 가장 작은 스코빌 지수 first와 두 번째로 작은 스코빌 지수 second를 꺼냅니다.
    const first = minHeap.pop();
    const second = minHeap.pop();

    // 섞은 음식의 스코빌 지수 mixed를 계산합니다.
    const mixed = first + second * 2;

    // mixed를 다시 minHeap에 삽입합니다.
    minHeap.push(mixed);

    // 섞은 횟수 count를 1 증가시킵니다.
    count++;
  }

  // while 반복문이 종료되면 모든 음식의 스코빌 지수가 K 이상이 된 것입니다.
  // 그러므로 섞은 횟수 count를 반환합니다.
  return count;
}

 

 

 

Heap 알고리즘을 처음 풀어봐서 아직 이해가 되지 않는다. 설명 차근차근 읽어보면서 이해하고, Heap 알고리즘에 대해서 자세히 찾아봐야겠다.

 

 

[프로그래머스] 주식가격 (LV2 - JavaScript)

 

[프로그래머스] 땅따먹기 (LV2 - JavaScript)