[백준] 1461 도서관 (Javascript)

문제

BOJ1461_도서관

풀이

요구사항

0번 위치에 책이 N개 있고, 각각의 책의 원위치가 정수로 주어진다. 한 번에 M개의 책을 들고 이동할 수 있을 때 0번 부터 모든 책을 원위치 시키기 위해 필요한 최소 이동 거리를 구하시오.
(모든 책을 원위치 시킨 뒤에는 0번 위치로 돌아올 필요 없다.)

해결방안

입력값이 아래와 같다고 가정해보자.

5 5
1 2 3 4 5

이럴 땐 5번 위치로 가는 과정에서 1 2 3 4 번도 들르기 때문에 5번까지 한 번만 이동해주면 모든 책을 원위치 시킬 수 있다.

즉 가장 먼 위치가 K라고 했을 때, K로 이동하면서 0~K가 원위치인 책들도 원위치 시킬 수 있다. 다만 한 번에 들고갈 수 있는 책의 개수가 제한 되기 때문에 여러번 왔다 갔다 해야 하는 경우가 발생할 수도 있다.

5 2
1 2 3 4 5

예를 들어 위 입력값처럼 한 번에 들고 갈 수 있는 책의 개수가 2개로 제한된다면 0 -> 2 -> 0 -> 4 -> 0 -> 5 이렇게 이동하는 것이 최단 거리다.

이를 구현한다면 입력값으로 주어진 책의 위치를 내림차순(5 4 3 2 1)로 정렬한 뒤, i를 M씩 증가시키며 위치[i]에 있는 거리를 왕복이기 때문에 *2 씩 정답에 누적 시키고, 가장 먼 위치인 5를 정답에서 빼주면 답을 구할 수 있다.

또한 책의 원위치에는 음수도 포함되어 있으므로 음수와 양수를 따로 구분하여 정렬해줘야 한다.

최종 코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const books = input[1].split(' ').map(Number);

const positive = [];
const negative = [];

for (const book of books) {
    if (book > 0) positive.push(book);
    else negative.push(book * -1);
}
positive.sort((a, b) => b - a);
negative.sort((a, b) => b - a);

let answer = 0;
for (let i = 0; i < positive.length; i += M) {
    answer += positive[i] * 2;
}
for (let i = 0; i < negative.length; i += M) {
    answer += negative[i] * 2;
}

if (positive[0] === undefined) positive[0] = 0;
if (negative[0] === undefined) negative[0] = 0;

if (positive[0] > negative[0]) answer -= positive[0];
else answer -= negative[0];

console.log(answer);