백준 코딩테스트 1715 자바스크립트 node.js

 

 

 

진짜 제일 어려운 문제였다

 

문제 자체는 쉬운데 구현하는게 너무 어려웠던 것 같다.

 

정답을 보고 이해하는데도 엄청나게 오랜 시간이 걸렸다.

 

이 공부를 계속 하는게 맞나 싶을 정도로.. 

 

이 문제는 제일 작은 수 두개를 더해서 배열에 계속 쌓고 또 제일 작은 두 수를 더해서 배열에 쌓고 하는 방식으로 푼다.

 

이걸 생코딩으로 풀어버리면 시간초과로 오답처리가 된다.

 

그래서 최소힙 이라는 알고리즘으로 풀어야 한다.

 

문과인 나에게는 처음들어보는 멍멍이 소리였다.

 

아래 블로그를 보았고 이해하는데 큰 도움이 되었다.

 

아래 블로그에서 개념을 잡고 넘어가시길 강력히 추천드린다.

 

https://reakwon.tistory.com/42

[자료구조] 그림으로 쉽게 보는 힙(Heap) 개념과 코드

 

코드

코드도 정답코드를 그대로 가져다가 썼다. 차마 안보고 구현하기가 아직은 힘들다.

 

대신 설명을 잘 해보겠다.

//let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let input= require('fs').readFileSync('./input.txt').toString().trim().split('\n');

//자바스크립트 클래스 생성
class MinHeap {
    //생성자
    constructor() {
      this.heap = [];
    }
    //힙 사이즈 크기 메서드
    getLength = () => {
      return this.heap.length;
    };
    //최초 값을 가져다가 배열에 넣을 푸쉬 메서드
    push = (node) => {
      //input값을 넣어준다.
      this.heap.push(node); 
      //배열은0부터 시작하지만 크기는 1부터 시작하기 때문에 -1 처리
      //현재 값을 넣어준 위치이다.
      let i = this.heap.length - 1;
      //부모의 위치
      let parentI = Math.floor((i - 1) / 2);
      //현재 위치에서부터 맨위 상위까지 루프를 돌면서 현재위치 자신의 값과 부모의값을 비교 후 치환
      while (i > 0 && this.heap[parentI] > this.heap[i]) {
        this.swap(i, parentI);
        i = parentI;
        parentI = Math.floor((i - 1) / 2);
      }
    };
    //가장 작은 수를 가져오고 다시 정렬하는 메서드
    pop = () => {
      //배열값이 하나뿐이면 그것이 최소값 -> 리턴
      if (this.heap.length === 1) {
        return this.heap.pop();
      }
      //맨위, 즉 제일 작은 값을 result에 저장한다.
      const result = this.heap[0]; 
     
     //그 후, 남은 값을 재정렬한다.
      this.heap[0] = this.heap.pop(); // 맨마지막 값을 맨 위로올려서
      let i = 0;
      //맨 위부터 루프를 돌면서 값을 치환한다.
      while (true) {
        const leftI = i * 2 + 1, 
          rightI = i * 2 + 2; 
        if (leftI >= this.heap.length) {   
          break;
        }
        let nextI = i;
        //왼쪽을 먼저 비교하고
        if (this.heap[nextI] > this.heap[leftI]) {
          nextI = leftI;
        }
        //오른쪽을 비교한다.
        if (rightI < this.heap.length && this.heap[nextI] > this.heap[rightI]) {
          nextI = rightI;
        }
        //값이 바뀌지 않았으면 리턴, 즉 현재 값이 더 작다는뜻
        if (nextI === i) {
          break;
        }
        this.swap(i, nextI);
        i = nextI;
      }
      return result;
    };
    //값을 스왑해주는 메서드
    swap = (a, b) => {
      const temp = this.heap[a];
      this.heap[a] = this.heap[b];
      this.heap[b] = temp;
    };
  }

sol(input);

function sol(input){
      const minHeap = new MinHeap();
      for (let i = 1; i < input.length; i++) {
        minHeap.push(+input[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);
}