세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.
상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)
다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)
다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)
모든 숫자는 양의 정수이다.
출력
첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.
====
문제 분석
가방 한 개를 딱 찝은 뒤에 그 가방에 가장 비싼 보석을 넣으면 되는 문제이다.
이 떄 가방 하나를 고른 뒤 보석을 하나하나 탐색 하는 행위는 O(n^2)이 되어 n이 30만인 문제에서 시간 초과 결과를 얻게 된다.
따라서 이를 최적화 해 줄 필요가 있는데 여기에서 보석의 무게를 탐색하는 행위를 줄이는 것으로 문제를 해결했다.
1. 가방과 보석의 정보를 각각 오름차순으로 정렬
이뗴 보석의 정보를 담은 배열은 보석의 무게를 기준으로 정렬한다.
2. 오름차순으로 정렬 된 가방을 하나하나 방문해보면서, 이 가방에 담을 수 있는 보석들을 모두 기록해둔다.
3. 담을 수 있는 보석들을 모두 기록했다면 이 중에서 가격이 제일 비싼 보석을 꺼내어 가방에 담아준다 -> 이 행위는 answer라는 배열에 담아준다.
4. 다음 가방을 탐색 했을 때에는 이전 과정에서 탐색했던 보석의 다음 정보부터 탐색해가며 담을 수 있는 것들을 기록.
이 때 기록하는 배열은 이전 과정에서의 기록지에다가 이어서 기록해야한다. 그래야 지금의 가방에 담을 수 있는 모든 보석들을 기록한 뒤에 가장 비싼 보석을 추출할 때에 이전 탐색에서 발견했었던 보석들과 합하여 제일 비싼 것을 추출할 수 있기 때문이다.
모든 가방을 탐색했다면 answer에 기록된 모든 값을 합하여 출력해준다.
1. 가방과 보석의 정보를 각각 오름차순으로 정렬
const input = require('fs')
.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
.toString()
.trim()
.split('\n');
const [n, k] = input[0].split(' ').map(Number);
const gems = input
.slice(1, n + 1)
.map((s) => s.split(' ').map(Number))
.sort((a, b) => a[0] - b[0]);
const bags = input
.slice(n + 1, n + k + 1)
.map(Number)
.sort((a, b) => a - b);2. 오름차순으로 정렬 된 가방을 하나하나 방문해보면서, 이 가방에 담을 수 있는 보석들을 모두 기록해둔다.
이 때 필요한 상태값은 어느 보석까지 탐색했는지 정보를 담은 gemIdx와 보석들을 담으면서 최종적으로는 그 보석 중 가장 비싼 가격을 내뱉을 우선순위 큐가 필요하다.
let gemIdx = 0;
const maxHeap = new MaxHeap();
const answer = [];js에는 우선순위 큐 메서드가 따로 없으므로 직접 구현.
push는 배열 마지막에 값을 넣은 후 자신의 부모와 비교해가며 자신이 더 크다면 swap ->upLevel
pop은 루트(가장 큰 값)를 빼주고 그 위치에 힙의 가장 마지막 값으로 넣어준 뒤 두 자식 중 가장 큰 값을 가진 자식과 swap ->downLevel
class MaxHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this.upLevel();
}
pop() {
if (this.heap.length === 0) return null;
const max = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.downLevel();
}
return max;
}
upLevel() {
let idx = this.heap.length - 1;
const element = this.heap[idx];
while (idx > 0) {
let parentIdx = Math.floor((idx - 1) / 2);
let parent = this.heap[parentIdx];
if (element <= parent) break;
this.heap[parentIdx] = element;
this.heap[idx] = parent;
idx = parentIdx;
}
}
downLevel() {
let idx = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIdx < length) {
leftChild = this.heap[leftChildIdx];
if (leftChild > element) swap = leftChildIdx;
}
if (rightChildIdx < length) {
rightChild = this.heap[rightChildIdx];
if (
(swap === null && rightChild > element) ||
(swap !== null && rightChild > leftChild)
) {
swap = rightChildIdx;
}
}
if (swap === null) break;
this.heap[idx] = this.heap[swap];
this.heap[swap] = element;
idx = swap;
}
}
get size() {
return this.heap.length;
}
}
3. 담을 수 있는 보석들을 모두 기록했다면 이 중에서 가격이 제일 비싼 보석을 꺼내어 가방에 담아준다 -> 이 행위는 answer라는 배열에 담아준다.
4. 다음 가방을 탐색 했을 때에는 이전 과정에서 탐색했던 보석의 다음 정보부터 탐색해가며 담을 수 있는 것들을 기록.
for (const bag of bags) {
while (gemIdx < gems.length && gems[gemIdx][0] <= bag) {
maxHeap.push(gems[gemIdx][1]);
gemIdx++;
}
if (maxHeap.size > 0) {
answer.push(maxHeap.pop());
}
}if문을 통해 지금까지 살펴본 보석 중 가장 비싼 것을 answer에 기록할 수 있는 것.
아래는 정답 출력 코드이다.
console.log(answer.reduce((acc, cur) => acc + cur, 0));정답 코드
class MaxHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this.upLevel();
}
pop() {
if (this.heap.length === 0) return null;
const max = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.downLevel();
}
return max;
}
upLevel() {
let idx = this.heap.length - 1;
const element = this.heap[idx];
while (idx > 0) {
let parentIdx = Math.floor((idx - 1) / 2);
let parent = this.heap[parentIdx];
if (element <= parent) break;
this.heap[parentIdx] = element;
this.heap[idx] = parent;
idx = parentIdx;
}
}
downLevel() {
let idx = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIdx < length) {
leftChild = this.heap[leftChildIdx];
if (leftChild > element) swap = leftChildIdx;
}
if (rightChildIdx < length) {
rightChild = this.heap[rightChildIdx];
if (
(swap === null && rightChild > element) ||
(swap !== null && rightChild > leftChild)
) {
swap = rightChildIdx;
}
}
if (swap === null) break;
this.heap[idx] = this.heap[swap];
this.heap[swap] = element;
idx = swap;
}
}
get size() {
return this.heap.length;
}
}
const input = require('fs')
.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
.toString()
.trim()
.split('\n');
const [n, k] = input[0].split(' ').map(Number);
const gems = input
.slice(1, n + 1)
.map((s) => s.split(' ').map(Number))
.sort((a, b) => a[0] - b[0]);
const bags = input
.slice(n + 1, n + k + 1)
.map(Number)
.sort((a, b) => a - b);
let gemIdx = 0;
const maxHeap = new MaxHeap();
const answer = [];
for (const bag of bags) {
while (gemIdx < gems.length && gems[gemIdx][0] <= bag) {
maxHeap.push(gems[gemIdx][1]);
gemIdx++;
}
if (maxHeap.size > 0) {
answer.push(maxHeap.pop());
}
}
console.log(answer.reduce((acc, cur) => acc + cur, 0));'코딩 테스트 > 백준' 카테고리의 다른 글
| 2164 카드2 (0) | 2025.04.18 |
|---|---|
| 2668 숫자고르기 (0) | 2025.04.17 |
| 2109 순회 강연 (자바스크립트) (1) | 2025.04.15 |
| 15486 퇴사 2 ( 자바스크립트 ) (0) | 2025.03.14 |
| 1766 문제집 (1) | 2025.03.14 |
