[JavaScript/node.js] 백준 14943번 - 벼룩 시장

[문제]

https://www.acmicpc.net/problem/14943

14943번: 벼룩 시장

[풀이]

+값은 판매 배열(sale[]), -값은 구매 배열(buy[])에 각각 저장한 후 투포인터를 활용하여 문제를 해결하였습니다.

 

1. info[]에 담겨있는 벼룩 시장 정보들을 sale과 buy에 [금액, index] 형태로 저장합니다.

 

2. 판매 정보와 구매 정보로 투포인터를 진행합니다.

• buy의 위치를 저장한 left 변수와, sale의 위치를 저장한 right 변수를 각각 0으로 초기화 합니다.
• buy의 left 금액과 sale의 right금액을 비교하여 비용 total과 left, right를 갱신합니다.
  • buy의 금액과 sale의 금액이 같다면 판매하는 벼룩을 모두 구매하였으므로 left와 right를 모두 +1
    => 비용은 [left가 바라보는 buy의 index - right가 바라보는 sale의 index| * 구매/판매 금액
  • buy금액이 더 크다면 sale의 벼룩을 모두 판매하고 right++
    => 비용은 [left가 바라보는 buy의 index - right가 바라보는 sale의 index| * 판매 금액
    => buy 금액에서 sale이 판매한 금액만큼 빼서 갱신
  • sale금액이 더 크다면 buy의 벼룩을 모두 구매하고 left++
    =>  비용은 [left가 바라보는 buy의 index - right가 바라보는 sale의 index| * 구매 금액
    => sale 금액에서 buy가 구매한 금액만큼 빼서 갱신

따라서 다음과 같이 계산하면 최소 비용은 950이 됩니다.

 

[코드]

// 벼룩 시장
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';

const input = fs.readFileSync(filePath).toString().split('\n');

const [N] = input[0].split(" ").map(Number);
const info = input[1].split(" ").map(Number);

const buy = [];
const sale = [];

for(let i=0;i<info.length;i++) {
    if(info[i] > 0) {
        sale.push([info[i], i]);
    } else {
        buy.push([info[i], i]);
    }
}

let left = 0;
let right = 0;
let total = 0;

while(left < buy.length && right < sale.length) {
    const diff = Math.abs(buy[left][0] + sale[right][0]);

    if(diff == 0) {
        // 판매 금액 === 구매 금액
        total += sale[right][0] * Math.abs(buy[left][1] - sale[right][1]);
        left++;
        right++;
    } else if(buy[left][0] + sale[right][0] < 0) {
        // 구매 금액이 더 큼
        total += sale[right][0] * Math.abs(buy[left][1] - sale[right][1]);
        buy[left][0] = diff*-1;
        right++;
    } else if(buy[left][0] + sale[right][0] > 0) {
        // 판매 금액이 더 큼
        total += buy[left][0] * -1 * Math.abs(buy[left][1] - sale[right][1]);
        sale[right][0] = diff;
        left++;
    }
}

console.log(total);