파일 합치기 3
📚 문제 설명
문제의 내용을 간략히 설명하면 다음과 같다.
- 파일을 합쳐야 하고 파일의 크기가 각각 주어진다. (ex:
[40, 30, 30, 50]) - 파일을 하나로 합치고 싶다.
- 파일 합치는 비용은 크기와 비례할 때, 비용이 최소가 되게 하여라
예시
파일 : [40, 30, 30, 50]
30 두개를 먼저 합치면
30 + 30 = 60
파일 : [40, 60, 50]
60과 40을 합치면
40 + 60 = 100
파일 : [100, 50]
100 + 50 = 150
전체 비용 = 60 + 100 + 150 = 310
---
그러나 최소가 되게 하려면 다음과 같다.
파일 : [40, 30, 30, 50]
40과 30을 합침
30 + 40 = 70
파일 : [30, 50, 70]
30과 50을 합치면
30 + 50 = 80
파일 : [70, 80]
70 + 80 = 150
전체 비용 = 70 + 80 + 150 = 300👨🏻💻 풀이 과정
이 문제는 이전에 풀었던 카드 정렬하기 문제랑 거의 똑같다고 해도 될 정도로 유사한 문제이다.
따라서 이 문제도 해당 문제에서와 같은 로직으로 풀면 될 것이다.
파일 합치기 과정을 거칠 때마다 각각의 파일의 비용을 더해주는 횟수를 나타낸 표.
| A+B | (A+B) + C | (A+B+C)+ D | |
|---|---|---|---|
| A | + | + + | + + + |
| B | + | + + | + + + |
| C | + | + + | |
| D | + |
위의 표를 보면 알 수 있듯, 파일을 하나로 합치기 위해서는 A < B < C < D 일 경우가 비용이 최소가 되는 것을 알 수 있다. ( 더하는 횟수가 많을 수록 크기가 작아야하기 때문)
따라서 이 문제는 Priority Queue( 우선 순위 큐 ) 를 이용하여 크기가 작은 순으로 나열한 후 작은순으로 2개씩 꺼내서 더해주면 될 것이다.
우선 전체 로직을 확인해보자.
전체 로직 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const TEST = input.shift();
let answer = '';
class MINHEAP {
// 생략
}
// 전체 테스트를 다 할 때까지 반복
while (input.length) {
// 테스트 입력을 2개씩 자름
let [N, Arr] = input.splice(0, 2);
// 문자열을 숫자로 이루어진 배열로 만들기 위해
Arr = Arr.split(' ').map(Number);
// 비용을 계속 더해줄 변수
let Acc = 0;
const MinHeap = new MINHEAP();
// MinHeap 에 모든 값을 넣어줌
for (const ELEMENT of Arr) {
MinHeap.Insert(ELEMENT);
}
// 우선순위큐(최소힙)의 크기가 1이 되면 모든 과정을 끝낸 것이기 때문에 크기가 1이 되면 종료
while (MinHeap.GetLength() > 1) {
// 비용
let temp = 0;
// 2개를 뽑아서 더해줌
temp += MinHeap.Pop();
temp += MinHeap.Pop();
// 2개의 파일을 합친 결과를 다시 큐에 삽입
MinHeap.Insert(temp);
// 비용을 매번 더해줌
Acc += temp;
}
answer += `${Acc}\n`;
}
console.log(answer);
Priority Queue를 구현하는 부분은 이전에 작성했던 포스트를 참고하면 될 것이고, 해당 포스트에서는 과정을 간략하게만 설명하겠다.
Priority Queue의 경우 JavaScript에서는 직접 구현을 해야한다. 따라서 Min Heap을 이용하여 구현을 진행해야 하는데,
[null] 을 이용하여 인덱스가 1부터 시작하는 배열을 이용하여
왼쪽 자식 노드 = 부모 노드 2
오른쪽 자식 노드 = 부모 노드 2 + 1
이 되도록 만들었다는 것을 유념하여 코드를 보면 이해가 빠를 것이다.
Priority Queue ( Min Heap ) 구현
class MINHEAP {
constructor() {
this.heap = [null];
}
Insert(item) {
// 끝 부분에 삽입을 하여 자신의 위치를 찾아갈 것이다.
let cur = this.heap.length;
// 정렬 과정
while (cur > 1) {
const parent = Math.floor(cur / 2);
if (this.heap[parent] > item) {
this.heap[cur] = this.heap[parent];
cur = parent
}else break;
}
// 알맞은 위치에 값 삽입
this.heap[cur] = item;
}
Pop(){
// 힙의 최상단 값 저장
const PopItem = this.heap[1];
if (this.heap.length > 2) {
// 최상단 값을 끝부분에서 가져와 바꿔줌 (그 후에 정렬 예정)
this.heap[1] = this.heap.pop();
// 부모 노드부터 내려가며 비교할 예정
let Current = 1;
let LeftChild = Current * 2;
let RightChild = Current * 2 + 1;
// 왼쪽 자식부터 가득 차게되는 트리 구조이기 때문에 자식 노드가 있는지는 왼쪽 자식만 확인하면 알 수 있다.
while (this.heap[LeftChild]) {
let ComparedChild = LeftChild;
// 왼쪽 자식과 오른쪽 자식을 비교하여 어떤 자식과 비교할지 선택
if (this.heap[RightChild] && this.heap[LeftChild] > this.heap[RightChild]) {
ComparedChild = RightChild;
}
// 비교할 자식과 비교후 조건에 맞으면 교체
if (this.heap[Current] > this.heap[ComparedChild]) {
[this.heap[Current], this.heap[ComparedChild]] = [this.heap[ComparedChild], this.heap[Current]];
}else break;
// 교체 후, 다시 자식과 비교를 위해 변수를 바꿔줌
Current = ComparedChild;
LeftChild = Current * 2;
RightChild = Current * 2 + 1;
}
}else if (this.heap.length === 2) {
this.heap.pop();
return PopItem;
} else {
return null;
}
return PopItem;
}
GetLength() {
return this.heap.length - 1;
}
}그럼 이제 전체 코드를 확인하면 다음과 같다.
전체 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const TEST = input.shift();
let answer = '';
class MINHEAP {
constructor() {
this.heap = [null];
}
Insert(item) {
// 끝 부분에 삽입을 하여 자신의 위치를 찾아갈 것이다.
let cur = this.heap.length;
// 정렬 과정
while (cur > 1) {
const parent = Math.floor(cur / 2);
if (this.heap[parent] > item) {
this.heap[cur] = this.heap[parent];
cur = parent
}else break;
}
// 알맞은 위치에 값 삽입
this.heap[cur] = item;
}
Pop(){
// 힙의 최상단 값 저장
const PopItem = this.heap[1];
if (this.heap.length > 2) {
// 최상단 값을 끝부분에서 가져와 바꿔줌 (그 후에 정렬 예정)
this.heap[1] = this.heap.pop();
// 부모 노드부터 내려가며 비교할 예정
let Current = 1;
let LeftChild = Current * 2;
let RightChild = Current * 2 + 1;
// 왼쪽 자식부터 가득 차게되는 트리 구조이기 때문에 자식 노드가 있는지는 왼쪽 자식만 확인하면 알 수 있다.
while (this.heap[LeftChild]) {
let ComparedChild = LeftChild;
// 왼쪽 자식과 오른쪽 자식을 비교하여 어떤 자식과 비교할지 선택
if (this.heap[RightChild] && this.heap[LeftChild] > this.heap[RightChild]) {
ComparedChild = RightChild;
}
// 비교할 자식과 비교후 조건에 맞으면 교체
if (this.heap[Current] > this.heap[ComparedChild]) {
[this.heap[Current], this.heap[ComparedChild]] = [this.heap[ComparedChild], this.heap[Current]];
}else break;
// 교체 후, 다시 자식과 비교를 위해 변수를 바꿔줌
Current = ComparedChild;
LeftChild = Current * 2;
RightChild = Current * 2 + 1;
}
}else if (this.heap.length === 2) {
this.heap.pop();
return PopItem;
} else {
return null;
}
return PopItem;
}
GetLength() {
return this.heap.length - 1;
}
}
// 전체 테스트를 다 할 때까지 반복
while (input.length) {
// 테스트 입력을 2개씩 자름
let [N, Arr] = input.splice(0, 2);
// 문자열을 숫자로 이루어진 배열로 만들기 위해
Arr = Arr.split(' ').map(Number);
// 비용을 계속 더해줄 변수
let Acc = 0;
const MinHeap = new MINHEAP();
// MinHeap 에 모든 값을 넣어줌
for (const ELEMENT of Arr) {
MinHeap.Insert(ELEMENT);
}
// 우선순위큐(최소힙)의 크기가 1이 되면 모든 과정을 끝낸 것이기 때문에 크기가 1이 되면 종료
while (MinHeap.GetLength() > 1) {
// 비용
let temp = 0;
// 2개를 뽑아서 더해줌
temp += MinHeap.Pop();
temp += MinHeap.Pop();
// 2개의 파일을 합친 결과를 다시 큐에 삽입
MinHeap.Insert(temp);
// 비용을 매번 더해줌
Acc += temp;
}
answer += `${Acc}\n`;
}
console.log(answer);
🧐 후기
문제를 제출했는데 채점 속도가 너무 늦어서 혹시 반복문을 너무 많이 사용해서 시간초과가 나는건가 조마조마 했었다.
채점이 완료 된 후에도 시간이 2000ms가 넘게 걸린 것을 보고 뭔가 잘못 풀었나 하는 마음에 채점 현황으로 들어가서 확인을 해보니, 다른 사람들도 다들 비슷하게 걸리는 것을 확인한 후에 다행이라고 느꼈다.
아무래도 문제 자체가 반복문이 많이 들어갈 수 밖에 없어서 시간이 좀 걸리는 것 같다.
JavaScript를 사용하는 모두를 위해...