[JS] 백준 1715번 - 카드 정렬하기 - 우선순위 큐, 최소 힙

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

 

우선순위 큐를 활용해야하는 문제이다.

 

📋풀이방법

1.최소힙 구조로 우선순위 큐에 주어진 값을 넣고, 루트노드를 두 개 A와 B의 뺀 값 C를 total값에 누적하고, 다시 최소힙에 더한 값 total을 넣으면 원하는 결과가 나온다.

2. 이 때 중요한 것은 우선순위큐 구조를 만드는 것이다.

 

https://chamdom.blog/heap-using-js/

[자료구조] JavaScript로 힙(Heap) 구현하기

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

let N = Number(input[0]);
let arr = [];
for (let i = 0; i < N; i++) {
  arr[i] = Number(input[i + 1]);
}
class MinHeap {
  constructor() {
    this.heap = [];
  }

  getLength = () => {
    return this.heap.length;
  };

  push = (node) => {
    this.heap.push(node);
    this.bubbleUp();
  };
  //bubbleUp이란
  /*
  힙에 값을 삽입할 때 부모와 비교해서 값이 크거나 작으면(최소 힙의 경우 부모가 자신보다 크면, 최대 힙의 경우 부모가 자신보다 작으면) 
  부모와 값을 교환해서 올바르게 정렬이 될 때 까지 올라가는 것을 bubbleUp이라 한다.
   */
  bubbleUp() {
    let i = this.heap.length - 1;
    let parentI = Math.floor((i - 1) / 2);
    while (
      this.heap[parentI] && //부모노드가 존재하고
      this.heap[parentI] > this.heap[i] //새로운 노드가 부모노드보다 작은경우
    ) {
      this.swap(i, parentI); //두 노드 값을 교체
      i = parentI;
      parentI = Math.floor((i - 1) / 2);
    }
  }
  //bubbleDown이란
  /*
  루트 노드를 삭제하고 마지막 노드를 루트로 올리고 루트 노드와 아래 자식 노드들과 비교해서 값이 크거나 작으면(최소 힙의 경우 자식이 자신보다 값이 작으면, 최대 힙의 경우 자식이 자신보다 값이 크면) 
  자식과 값을 교환해서 올바르게 정렬이 될 때 까지 내려가는 것을 bubbleDown이라 한다.
  */
  pop = () => {
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const result = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return result;
  };
  bubbleDown() {
    let i = 0; // 루트 노드의 index
    let leftI = i * 2 + 1, // 왼쪽 자식 노드의 index
      rightI = i * 2 + 2; // 오른쪽 자식 노드의 index
    while (
      // 왼쪽 자식 노드가 존재 하면서 값이 루트 노드보다 작거나
      (this.heap[leftI] && this.heap[leftI] < this.heap[i]) ||
      // 오른쪽 자식 노드가 존재 하면서 값이 루트 노드보다 작은 경우
      (this.heap[rightI] && this.heap[rightI] < this.heap[i])
    ) {
      let smallerIdx = leftI; // 왼쪽 자식 노드가 더 작다고 가정
      if (
        this.heap[rightI] &&
        this.heap[rightI] < this.heap[smallerIdx] // 오른쪽 자식 노드가 더 작다면
      ) {
        smallerIdx = rightI; // 오른쪽 자식 노드의 index로 변경
      }
      this.swap(i, smallerIdx);
      i = smallerIdx;
      leftI = i * 2 + 1; // 왼쪽 자식 노드의 index 계산
      rightI = i * 2 + 2; // 오른쪽 자식 노드의 index 계산
    }
  }

  swap = (a, b) => {
    const temp = this.heap[a];
    this.heap[a] = this.heap[b];
    this.heap[b] = temp;
  };
}

const minHeap = new MinHeap();
for (let i = 0; i < N; i++) {
  minHeap.push(arr[i]);
}

let totalCompareCount = 0;
//힙안의 값이 하나가 될 때 까지
while (minHeap.getLength() > 1) {
  let aCount = minHeap.pop(); //최소힙이므로
  let bCount = minHeap.pop(); //루트노드를 두개 빼온다
  let compareCount = aCount + bCount; //그 최솟값 두 개를 더하고
  totalCompareCount += compareCount; //누적한다.
  minHeap.push(compareCount); //누적값을 다시 힙에 넣어서 정렬된다.
}
console.log(totalCompareCount);

 

 

💢어려웠던 점

1. 아직 우선순위큐에 대해서 숙지하지 못했다.

2. 최소힙과 최대힙의 차이를 숙지하자

-최소힙과 최대힙의 차이는 bubbleUp과 bubbleDown의  차이이다.

-아래 코드를 추가해봤다.

-주석처리한 곳을 사용하면 최대힙으로 사용가능하다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

let N = Number(input[0]);
let arr = [];
for (let i = 0; i < N; i++) {
  arr[i] = Number(input[i + 1]);
}
class MinHeap {
  constructor() {
    this.heap = [];
  }

  getLength = () => {
    return this.heap.length;
  };

  push = (node) => {
    this.heap.push(node);
    this.bubbleUp();
  };
  //bubbleUp이란
  /*
  힙에 값을 삽입할 때 부모와 비교해서 값이 크거나 작으면(최소 힙의 경우 부모가 자신보다 크면, 최대 힙의 경우 부모가 자신보다 작으면) 
  부모와 값을 교환해서 올바르게 정렬이 될 때 까지 올라가는 것을 bubbleUp이라 한다.
   */
  bubbleUp() {
    let i = this.heap.length - 1;
    let parentI = Math.floor((i - 1) / 2);
    while (
      this.heap[parentI] && //부모노드가 존재하고
      this.heap[parentI] > this.heap[i] //새로운 노드가 부모노드보다 작은경우
    ) {
      this.swap(i, parentI); //두 노드 값을 교체
      i = parentI;
      parentI = Math.floor((i - 1) / 2);
    }
  }
  //bubbleDown이란
  /*
  루트 노드를 삭제하고 마지막 노드를 루트로 올리고 루트 노드와 아래 자식 노드들과 비교해서 값이 크거나 작으면(최소 힙의 경우 자식이 자신보다 값이 작으면, 최대 힙의 경우 자식이 자신보다 값이 크면) 
  자식과 값을 교환해서 올바르게 정렬이 될 때 까지 내려가는 것을 bubbleDown이라 한다.
  */
  pop = () => {
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const result = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return result;
  };
  bubbleDown() {
    let i = 0; // 루트 노드의 index
    let leftI = i * 2 + 1, // 왼쪽 자식 노드의 index
      rightI = i * 2 + 2; // 오른쪽 자식 노드의 index
    while (
      // 왼쪽 자식 노드가 존재 하면서 값이 루트 노드보다 작거나
      (this.heap[leftI] && this.heap[leftI] < this.heap[i]) ||
      // 오른쪽 자식 노드가 존재 하면서 값이 루트 노드보다 작은 경우
      (this.heap[rightI] && this.heap[rightI] < this.heap[i])
    ) {
      let smallerIdx = leftI; // 왼쪽 자식 노드가 더 작다고 가정
      if (
        this.heap[rightI] &&
        this.heap[rightI] < this.heap[smallerIdx] // 오른쪽 자식 노드가 더 작다면
      ) {
        smallerIdx = rightI; // 오른쪽 자식 노드의 index로 변경
      }
      this.swap(i, smallerIdx);
      i = smallerIdx;
      leftI = i * 2 + 1; // 왼쪽 자식 노드의 index 계산
      rightI = i * 2 + 2; // 오른쪽 자식 노드의 index 계산
    }
  }

  swap = (a, b) => {
    const temp = this.heap[a];
    this.heap[a] = this.heap[b];
    this.heap[b] = temp;
  };
  //최대힙과 최소힙의 차이는 bubbleUP과 bubbelDown이 어떻게 되느냐의 차이다.
  // bubbleUp() {
  //   let index = this.heap.length - 1;
  //   let parentI = Math.floor((index - 1) / 2);
  //   while (
  //     this.heap[parentI] !== undefined &&
  //     this.heap[parentI] < this.heap[index]
  //   ) {
  //     this.swap(index, parentI);
  //     index = parentI;
  //     parentI = Math.floor((index - 1) / 2);
  //   }
  // }

  // bubbleDown() {
  //   let index = 0;
  //   let leftI = index * 2 + 1, // 왼쪽 자식 노드의 index
  //     rightI = index * 2 + 2; // 오른쪽 자식 노드의 index
  //   while (
  //     this.heap[leftI] !== undefined &&
  //     (this.heap[leftI] > this.heap[index] ||
  //       this.heap[rightI] > this.heap[index])
  //   ) {
  //     let largerIndex = this.heap[leftI];
  //     if (
  //       this.heap[rightI] !== undefined &&
  //       this.heap[rightI] > this.heap[largerIndex]
  //     ) {
  //       largerIndex = this.heap[rightI];
  //     }
  //     this.swap(largerIndex, index);
  //     index = largerIndex;
  //     leftI = index * 2 + 1; // 왼쪽 자식 노드의 index 계산
  //     rightI = index * 2 + 2; // 오른쪽 자식 노드의 index 계산
  //   }
  // }
}

const minHeap = new MinHeap();
for (let i = 0; i < N; i++) {
  minHeap.push(arr[i]);
}

let totalCompareCount = 0;
//힙안의 값이 하나가 될 때 까지
while (minHeap.getLength() > 1) {
  let aCount = minHeap.pop(); //최소힙이므로
  let bCount = minHeap.pop(); //루트노드를 두개 빼온다
  let compareCount = aCount + bCount; //그 최솟값 두 개를 더하고
  totalCompareCount += compareCount; //누적한다.
  minHeap.push(compareCount); //누적값을 다시 힙에 넣어서 정렬된다.
}
console.log(totalCompareCount);