[백준 node.js] 1715번_카드 정렬하기

백준 그리디 알고리즘 1715번_카드 정렬하기

난이도 : 골드IV

문제 설명

추가 입출력예시

예제 입력 2 => 5 20 20 20 10 10   예제 출력2 => 180

 

문제 풀이 :  1. 입력 받은 카드 묶음에서 제일 작은거 두개를 빼낸다. 2. 두개를 덧셈 후 결과값을 누적 카운트 해주고 다시 카트 묶음에 넣어준다. 3.모든 묶음을 위의 과정대로 반복한다.

 

*최소힙 자료구조를 이용한 풀이(통과)

//최소힙 자료구조
function MinHeap() {
  this.heap = [0];
  this.insert = (v) => {
    this.heap.push(v);
    let p = this.heap.length - 1;
    while (p > 1 && this.heap[Math.floor(p / 2)] > this.heap[p]) {
      let tmp = this.heap[Math.floor(p / 2)];
      this.heap[Math.floor(p / 2)] = this.heap[p];
      this.heap[p] = tmp;
      p = Math.floor(p / 2);
    }
  };
  this.getLength = () => {
    return this.heap.length;
  };
  this.delete = () => {
    if (this.heap.length - 1 < 1) {
      return 0;
    }
    let deletedItem = this.heap[1];
    this.heap[1] = this.heap[this.heap.length - 1];
    this.heap.pop();
    let p = 1;
    while (p * 2 < this.heap.length) {
      let min = this.heap[p * 2];
      let minP = p * 2;
      if (p * 2 + 1 < this.heap.length && min > this.heap[p * 2 + 1]) {
        min = this.heap[p * 2 + 1];
        minP = p * 2 + 1;
      }
      if (this.heap[p] < min) {
        break;
      }
      let tmp = this.heap[p];
      this.heap[p] = this.heap[minP];
      this.heap[minP] = tmp;
      p = minP;
    }
    return deletedItem;
  };
}

const solution = (n, list) => {
  let cnt = 0;

  for (let i = 1; i < n; i++) {
    //제일 작은 카드 두개의 묶음을 빼낸다.
    let card1 = list.delete();
    let card2 = list.delete();
    //카드 두 묶음을 계산후 카운트
    let sum = card1 + card2;
    cnt += sum;
    //계산된 결과를 최소힙에 넣어줌
    list.insert(sum);
  }
  console.log(cnt);
};

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
rl.on("line", function (line) {
  //여러줄 입력
  input.push(line);
}).on("close", function () {
  let n = Number(input.shift());

  //최소힙 클래스 생성
  let list = new MinHeap();
  for (let i = 0; i < n; i++) {
    //최소힙을 이용하여 값을 하나씩 넣어준다.
    let tmp = Number(input.shift());
    list.insert(tmp);
  }
  solution(n, list);
  process.exit();
});

*처음에 시도한 풀이(메모리 초과로 실패)

const solution = (n, list) => {
  let cnt = 0;

  for (let i = 1; i < n; i++) {
    //오름차순 정렬
    list = list.sort((a, b) => a - b);
    //제일 앞에 두개가 작은 값이니깐 뺴준다.
    let card1 = list.shift();
    let card2 = list.shift();
    let sum = card1 + card2;
    cnt += sum;
    //배열 제일 앞에 넣어줌
    list.unshift(sum);
  }
  console.log(cnt);
};

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
rl.on("line", function (line) {
  //여러줄 입력
  input.push(line);
}).on("close", function () {
  let n = Number(input.shift());
  let list = input.map((el) => Number(el));
  solution(n, list);
  process.exit();
});

 

* 처음에는 위에 언급한 실패한 풀이로 풀었다. 한번의 과정마다 정렬을 해주고 메소드를 이용해 넣어주고 빼주고 반복했다. 제출하니깐 시간초과가 아닌 메모리 초과가 났다. 검색을 통해 찾아보니 역시나 값을 넣어주고 빼고 정렬땜에 메모리가 많이 잡아먹었던 것이였다. 그래서 JS 최소힙 자료구조를 찾아서 가져다써서 해결했다. 

(파이썬 코드를 보니깐 최소힙 구현없이 그냥 메소드처럼 불러서 사용하는 것을 보고 역시 파이썬....하고 파이썬이 간절했다ㅠㅠ)

앞으로 시간나면 JS 최소힙, 최대힙, 큐, 스택 등 여러 자료구조도 포스팅하면서 익히고 나중에 편히 가져다 쓰도록 해야겠다.