더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

 

 

이런식으로 풀었을 때 문제는

min의 참조가 불변한다는 문제가 있다

 

1, 3, 8, 14에서 실패하고 나머지는 성공하지만

효율성테스트에서는 런타임 에러가 뜬다

모든 음식을 K 이상으로 만들 수 없을 때는 -1을 반환해야 합니다. 라는 조건이 있었다

그래도 안된다 

AI 피드백 기능이 새로 생겼다

splice 가 효율성에 많은 영향을 끼치나 보다

 

좀 더 효율적으로 짜보기 위해

내림차순으로 정렬 한 후 가장 작은 수 2개를 뽑고

두개를 합친담에 새로운 배열값을 하나 추가하고 정렬하는 식으로 루프를 짜봤는데 

역시나 효율성에서는 실패

쥐쥐

결국 힙으로 처리...

힙 구현부가 너무 길어서 액기스만

나중에 다시 봐야할 문제

 

 

### 최소 힙 (Min Heap)

최소 힙은 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같은 완전 이진 트리입니다. 최소 힙에서 최상위 노드(루트 노드)는 항상 가장 작은 값을 가집니다. 이러한 특성 덕분에 최소 힙은 우선순위 큐의 구현에 자주 사용됩니다.

### 최소 힙의 특징

1. **완전 이진 트리**: 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워져 있습니다.
2. **힙 속성**: 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같습니다.

### 최소 힙의 주요 연산

1. **삽입 (Insert)**:
   - 새 요소를 힙의 마지막 위치에 삽입한 후, 힙 속성을 유지하기 위해 `heapifyUp` 연산을 수행합니다.
   
2. **삭제 (Delete)**:
   - 최상위 요소(최소값)를 제거하고, 힙의 마지막 요소를 루트로 이동시킨 후, 힙 속성을 유지하기 위해 `heapifyDown` 연산을 수행합니다.
   
3. **최소값 추출 (Extract-Min)**:
   - 최상위 요소를 반환합니다.

### 배열을 사용한 최소 힙 구현

최소 힙은 일반적으로 배열을 사용하여 구현됩니다. 이 배열 기반 구현에서는 특정 위치에 있는 노드의 부모와 자식 노드를 쉽게 찾을 수 있습니다.

- **부모 노드 인덱스**: `parent(i) = Math.floor((i - 1) / 2)`
- **왼쪽 자식 노드 인덱스**: `left(i) = 2 * i + 1`
- **오른쪽 자식 노드 인덱스**: `right(i) = 2 * i + 2`

### 최소 힙의 구현 예제

다음은 자바스크립트로 최소 힙을 구현한 예제입니다:

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

  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  getLeftChildIndex(index) {
    return 2 * index + 1;
  }

  getRightChildIndex(index) {
    return 2 * index + 2;
  }

  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }

  heappush(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = this.getParentIndex(index);
      if (this.heap[index] < this.heap[parentIndex]) {
        this.swap(index, parentIndex);
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  heappop() {
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();
    return minValue;
  }

  heapifyDown() {
    let index = 0;
    while (this.getLeftChildIndex(index) < this.heap.length) {
      let smallerChildIndex = this.getLeftChildIndex(index);
      if (this.getRightChildIndex(index) < this.heap.length && this.heap[this.getRightChildIndex(index)] < this.heap[smallerChildIndex]) {
        smallerChildIndex = this.getRightChildIndex(index);
      }
      if (this.heap[index] > this.heap[smallerChildIndex]) {
        this.swap(index, smallerChildIndex);
        index = smallerChildIndex;
      } else {
        break;
      }
    }
  }

  peek() {
    return this.heap[0];
  }

  size() {
    return this.heap.length;
  }
}
```

### 예제 사용

이제 최소 힙 클래스를 사용하여 간단한 예제를 실행해봅시다:

```javascript
const heap = new MinHeap();
heap.heappush(10);
heap.heappush(5);
heap.heappush(20);
heap.heappush(3);

console.log(heap.peek()); // 3
console.log(heap.heappop()); // 3
console.log(heap.peek()); // 5
console.log(heap.heappop()); // 5
console.log(heap.peek()); // 10
```

### 설명

1. **삽입 (`heappush`)**:
   - 새 값을 힙의 끝에 추가합니다.
   - `heapifyUp`을 통해 힙 속성을 유지합니다. 새 요소를 부모와 비교하여 필요할 경우 위치를 교환합니다.

2. **삭제 (`heappop`)**:
   - 최상위 요소(최소값)를 제거합니다.
   - 힙의 마지막 요소를 루트로 이동시킵니다.
   - `heapifyDown`을 통해 힙 속성을 유지합니다. 루트 요소를 자식들과 비교하여 필요할 경우 위치를 교환합니다.

3. **최소값 조회 (`peek`)**:
   - 힙의 최상위 요소를 반환합니다.

4. **힙 크기 조회 (`size`)**:
   - 힙의 크기를 반환합니다.

### 최적화

최소 힙을 사용하면 최솟값을 효율적으로 관리할 수 있으며, 배열을 정렬하여 최소값을 찾는 것보다 훨씬 더 빠른 시간복잡도를 가집니다. 이는 `scoville` 문제와 같은 우선순위 큐 문제를 해결하는 데 매우 유용합니다.