[Softeer] lv2. 금고털이 풀이 / Javascript

Softeer 금고털이

 

1. 문제

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

 

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

 

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

입력형식

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

출력형식

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

입력예제1

100 2 90 1 70 2

출력예제1

170

 

2. 언어별 시간 / 메모리

 

3. 풀이

고전적인 탐욕(Greedy) 문제 분할 가능 배낭 문제

 

처음 문제 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8');
const inputs = input.trim().split('\n');

const [first, ...args] = inputs;
let [w, n] = first.split(' ');
const items = args.map((v) => v.split(' ')).map(arr => [ Number(arr[0]), Number(arr[1]) ]).sort((a, b) => b[1] - a[1]);

let result = 0;
let index = 0;

while(true) {
    if (w <= 0 || index >= n) { 
        break; 
    }
    
    const item = items[index];

    if (w >= item[0]) {
        result += item[0] * item[1]
    } else {
        result += w * item[1]
    }

    w = w - item[0]
    index++;
}

console.log(result);

 

시간 복잡도: O(N logN)

 

하지만 메모리 256MB를 조과함.

이유는 최대 100만줄의 문자열 input을 처리하면서 발생. fs.readFileSync 방식 말고 readling 방식으로 처리하자.

 

관련 이슈 정리: https://nuhends.tistory.com/144

 

수정 후 풀이

const readline = require('readline');

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

let W = 0, N = 0;
const items = [];

rl.on('line', (line) => {
    // 첫번째 줄
    if (!W) {
        [W, N] = line.trim().split(' ').map(Number);
    } else {
        const [m, p] =line.trim().split(' ').map(Number);
        items.push([m, p]);

        if (items.length === N) {
            rl.close();
        }
    }
});

rl.on('close', () => {
    items.sort((a, b) => b[1] - a[1])

    let result = 0;

    for(let i=0; i<N && W > 0; i++) {
        const [m, p] = items[i];

        if (W >= m) {
            result += m * p;
            W -= m;
        } else {
            result += W * p;
            W = 0;
        }
    }

    console.log(result);
});