[백준] 1715번: 카드 정렬하기 (JavaScript, NodeJS)

문제

 

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

예제 입력 1 복사

3
10
20
40

예제 출력 1 복사

100

정답 풀이

처음 풀이

function solution(n, list) {
	let compareCount = 0;
	let sortedList = list;
	let beforeCount = 0;

	for (let i = 0; i < n - 1; i += 1) {
		sortedList = sortedList.sort((a, b) => a - b);

		const first = sortedList.shift();
		const second = sortedList.shift();

		beforeCount = first + second;
		sortedList.push(beforeCount);
		compareCount += beforeCount;

	}
}

처음에 문제를 풀었을 때는 아이디어는 정확하게 풀었다.

 

[10, 40, 70, 60] 이 있다면,

1. 배열을 오름차순 정렬한다.

현재 배열: [10, 40, 60, 70]

 

2. 배열에서 제일 작은 두 개의 값을 빼고(Pop을 해야한다.), 그 두 개를 더한다.

현재 배열: [60, 70]

10 + 40 = 50 (현재 비교횟수 50번)

 

3. 그 다음 더한 값을 배열에 넣어준다.

현재 배열:  [60, 70, 50]

 

그럼 다시 위의 과정을 N -1번 반복한다.

 

n = 0일 때,
10 + 40 = 50 (현재 비교횟수 50번)
[60, 70, 50]

n = 1일 때,
50 + 60 = 110 (현재 비교횟수 160번)
[70, 110]

n = 2일 때,
70 + 110 = 180 (현재 비교횟수 340번)[10, 40, 60, 70] 배열이 들어온다면 정답은 340이다.

 

아이디어는 정확하게 맞았는데 시간 초과가 떴다.

아마 자바스크립트 sort에서 시간을 많이 잡아먹는 것 같다.

정답

const fs = require("fs");

// 백준 제출 할 때 주석 제거
// const readFileSyncAddress = '/dev/stdin';

// VSC 테스트 할 때 주석 제거
const readFileSyncAddress = "input.txt";

const input = fs.readFileSync(readFileSyncAddress).toString().trim().split("\n");

let [n, ...list] = input;
list = list.map(i => Number(i));

class Heap {
	constructor(){
		this.items = [];
	}

	//값을 서로 바꾸는 메소드
	swap(index1, index2){
		let temp = this.items[index1]; // items의 index1의 값을 temp(임시공간)에 담음
		this.items[index1] = this.items[index2]; // index1에 index2의 값을 저장
		this.items[index2] = temp; // index2에 아까 index1의 값을 temp에 넣어놓은 값을 저장
	}

	//부모 인덱스 구하는 메소드
	findParentIndex(index){
		return Math.floor((index-1) / 2);
	}

	//왼쪽 자식 인덱스 구하는 메소드
	findLeftChildIndex(index){
		return index * 2 + 1;
	}

	//오른쪽 자식 인덱스 구하는 메소드
	findRightChildIndex(index){
		return index * 2 + 2;
	}

	//부모 노드 구하는 메소드
	findParent(index){
		return this.items[this.findParentIndex(index)];
	}

	//왼쪽 자식 노드 구하는 메소드
	findLeftChild(index){
		return this.items[this.findLeftChildIndex(index)];
	}

	//오른쪽 자식 노드 구하는 메소드
	findRightChild(index){
		return this.items[this.findRightChildIndex(index)];
	}

	//최대 힙의 경우 최댓값을 반환하고 최소 힙의 경우 최솟값을 반환하는 메소드
	peek(){
		return this.items[0];
	}

	//힙의 크기(항목 개수)를 반환하는 메소드
	size(){
		return this.items.length;
	}
}

class MinHeap extends Heap {
	// MinHeap 클래스는 Heap 클래스를 상속받았으므로 Heap 클래스의 메소드를 모두 사용할 수 있다.
	bubbleUp(){
		let index = this.items.length-1;
		while(this.findParent(index) !==undefined && this.findParent(index) > this.items[index]){
				this.swap(index, this.findParentIndex(index));
				index = this.findParentIndex(index);
		}
	}

	bubbleDown(){
		let index = 0;
		while(this.findLeftChild(index) !==undefined && (this.findLeftChild(index) < this.items[index] || this.findRightChild(index) < this.items[index])){
			let smallerIndex = this.findLeftChildIndex(index);
			if(this.findRightChild(index) !==undefined && this.findRightChild(index) < this.items[smallerIndex]){
					smallerIndex = this.findRightChildIndex(index);
			}
			this.swap(index, smallerIndex);
			index = smallerIndex;
		}
	}

	// 힙에 원소를 추가하는 함수
	add(item){
		this.items[this.items.length] = item;
		this.bubbleUp();
	}

	// 힙에서 원소를 빼내는 함수
	// 최소 힙이라면 최솟값이 빠져나올 것이고 최대힙이라면 최댓값이 빠져나온다.
	poll(){
		let item = this.items[0]; // 첫번째 원소 keep
		this.items[0] = this.items[this.items.length - 1]; // 맨 마지막 원소를 첫번째 원소로 복사
		this.items.pop(); // 맨 마지막 원소 삭제
		this.bubbleDown();
		return item; // keep해둔 값 반환
	}
}

// 문제 풀이
function solution(n, list) {
	let minHeap = new MinHeap();
	let compareCount = 0;
	let beforeCount = 0;

	for (let i = 0; i < n; i += 1) {
		minHeap.add(list[i]);
	}

	for (let i = 0; i < n - 1; i += 1) {
		const first = minHeap.poll();
		const second = minHeap.poll();

		beforeCount = first + second;
		minHeap.add(beforeCount);
		compareCount += beforeCount;
	}

	console.log(compareCount);
}

// 제출
solution(n, list);

 

자바스크립트 내장 sort 메소드를 이용하면 시간 초과가 나면서 문제가 풀리지 않는다.

그래서 minHeap을 사용하면, 정렬이 O(nlogN)이기 때문에 시간 초과가 나지않는다.

 

파이썬은 힙이 구현이 되어있지만, 자바스크립트는 스스로 구현해야 한다는 점...

나도 힙을 구현해본 적이 없어서 블로그를 참고했다.

 

최소힙, 최대힙 자바스크립트 구현 참고

 

힙에 대해서 공부하고, 최소힙 최대힙을 혼자 구현할 수 있게 해야할 것 같다.