[프로그래머스] 더 맵게

📖 문제

level2 더 맵게

✏️ 나의 풀이

문제는 최소힙만 구현하면 간단히 풀 수 있는 문제였다.

처음에는 최소힙이 아닌 정렬만을 이용해 풀려고 해보니, 당연하게도 시간초과가 발생했다.

Heap

constructor

constructor() {
    this.tree = [-1];
    this.size = 0;
}

• Heap 객체가 만들어 지면, 배열과 배열 안에 있는 요소 갯수인 size 변수를 선언 및 초기화 해준다.
• 1번 인덱스부터 사용할 것이기에 0번째 인덱스에는 -1을 넣어두었다.
  • scoville의 원소는 0이상 이기에 -1을 저장했다.

push

push(num) {
    this.tree.push(num);
    let index = this.size + 1;
    let parentIndex = Math.floor(index / 2);

    this.size += 1;

    while (index > 1) {
        const currentValue = num;
        const parentValue = this.tree[parentIndex];
        if (num <= parentValue) {
            this.swap(parentIndex, index);
            index = parentIndex;
            parentIndex = Math.floor(index / 2);
        } else break;
    }
}

• heap에 원소를 추가할 때 우선 가장 맨 뒤에 요소를 추가해준다.
• 그리고 이제 부모와 비교하며 heap을 정리해준다.
• 만일, 부모가 새로 추가된 원소보다 크면 둘의 값을 변경해준다.
• 그다음 index 값을 업데이트 해주며 계속 반복해준다.
• 만일, index 값이 1보다 작으면 트리의 가장 위에 존재하는 것이므로 반복문을 종료해준다.
• 또한, 부모의 값이 추가된 원소보다 작으면 더이상 값을 변경해줄 필요가 없으므로 반복문을 종료해준다.

pop

pop() {
    if (this.getSize() === 0) return null;
    if (this.getSize() === 1) {
        this.size -= 1;
        return this.tree.pop();
    }
    const last = this.tree.pop();
    const res = this.tree[1];

    this.tree[1] = last;
    this.size -= 1;

    let index = 1;
    let leftIndex = index * 2;
    let rightIndex = leftIndex + 1;

    while (
        (this.tree[leftIndex] && this.tree[leftIndex] < this.tree[index]) ||
        (this.tree[rightIndex] && this.tree[rightIndex] < this.tree[index])
    ) {
        let smallIndex = leftIndex;
        if (
            this.tree[rightIndex] &&
            this.tree[smallIndex] > this.tree[rightIndex]
        ) {
            smallIndex = rightIndex;
        }
        this.swap(index, smallIndex);
        index = smallIndex;

        leftIndex = index * 2;
        rightIndex = leftIndex + 1;
    }
    return res;
}

• 값을 제거할때 우선 this.size 가 0이면 값이 없으므로 null을 반환한다.
• this.size가 1이면 값이 하나 이므로 this.size값을 1감소시키고 배열의 마지막 값을 반환한다.
• 위 두 조건에 충족하지 않은 경우

• 배열의 마지막 값을 this.tree[1]에 넣어두고 기존 this.tree[1] 값은 최종적으로 반환해주기 위해 저장해둔다.

• 이제 반복문을 돌리며 this.tree[1]에 있는 값을 올바른 자리에 정렬해두기 위해 반복문을 돌린다.

while (
        (this.tree[leftIndex] && this.tree[leftIndex] < this.tree[index]) ||
        (this.tree[rightIndex] && this.tree[rightIndex] < this.tree[index])
    )

• 반복문의 조건은 왼쪽 자식이 존재하며, 왼쪽 자식의 값이 부모의 값보다 작거나,
• 오른쪽 자식이 존재하며, 오른쪽 자식의 값이 부모의 값보다 작아야한다.
• 위 두 조건 모두 만족하지 못하면 더이상 변경시킬 값이 없으므로 반복문을 종료한다.

let smallIndex = leftIndex;
if (
    this.tree[rightIndex] &&
    this.tree[smallIndex] > this.tree[rightIndex]
) {
    smallIndex = rightIndex;
}
this.swap(index, smallIndex);
index = smallIndex;

leftIndex = index * 2;
rightIndex = leftIndex + 1;

• 반복문 내부에서는 위 코드가 동작한다.
• 우선 왼쪽 자식의 값이 오른쪽 값보다 작다고 가정을 한다.
  • smallIndex 는 값이 작은 index를 의미한다.
• 그 다음 오른쪽 자식이 존재하고, 오른쪽 자식의 값이 왼쪽 자식의 값보다 작으면 smallIndex를 rightIndex로 변경한다.

this.swap(index, smallIndex);
index = smallIndex;

leftIndex = index * 2;
rightIndex = leftIndex + 1;

• 그 다음 두 값을 교체하며 index값을 업데이트 시킨다.

👩‍💻 코드

class Heap {
  constructor() {
    this.tree = [-1];
    this.size = 0;
  }

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

  push(num) {
    this.tree.push(num);
    let index = this.size + 1;
    let parentIndex = Math.floor(index / 2);

    this.size += 1;

    while (index > 1) {
      const currentValue = num;
      const parentValue = this.tree[parentIndex];
      if (num <= parentValue) {
        this.swap(parentIndex, index);
        index = parentIndex;
        parentIndex = Math.floor(index / 2);
      } else break;
    }
  }

  pop() {
    if (this.getSize() === 0) return null;
    if (this.getSize() === 1) {
      this.size -= 1;
      return this.tree.pop();
    }
    const last = this.tree.pop();
    const res = this.tree[1];

    this.tree[1] = last;
    this.size -= 1;

    let index = 1;
    let leftIndex = index * 2;
    let rightIndex = leftIndex + 1;

    while (
      (this.tree[leftIndex] && this.tree[leftIndex] < this.tree[index]) ||
      (this.tree[rightIndex] && this.tree[rightIndex] < this.tree[index])
    ) {
      let smallIndex = leftIndex;
      if (
        this.tree[rightIndex] &&
        this.tree[smallIndex] > this.tree[rightIndex]
      ) {
        smallIndex = rightIndex;
      }
      this.swap(index, smallIndex);
      index = smallIndex;

      leftIndex = index * 2;
      rightIndex = leftIndex + 1;
    }
    return res;
  }

  getSize() {
    return this.size;
  }

  isCheck(K) {
    for (let i = 1; i < this.tree.length; i++) {
      if (this.tree[i] < K) return false;
    }
    return true;
  }
  print() {
    console.log(this.tree);
  }
}

function solution(scoville, K) {
  let answer = 0;
  const heap = new Heap();
  scoville.forEach((v) => {
    heap.push(v);
  });

  while (!heap.isCheck(K)) {
    const food1 = heap.pop();
    const food2 = heap.pop();
    if (!food1 || !food2) return -1;

    const newFood = food1 + food2 * 2;
    heap.push(newFood);
    answer += 1;
  }

  return answer;
}