[ 𝗕𝗢𝗝 ] 1461번 도서관 - 그리디 | JavaScript

🎯 문제 설명

🧩 백준 1461번 - 도서관 | 골드4

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

입력

• 첫째 줄
  • 책의 개수 N (N ≤ 50)
  • 세준이가 한 번에 들수 있는 책의 개수 M (M ≤ 50)
• 둘째 줄 : 책의 위치 (not 0, and |n| ≤ 10,000)

7 2
-37 2 -6 -39 -29 11 -28

출력

첫째 줄에 정답을 출력한다.

131

👩🏻‍💻 문제 풀이

우선 책들이 0에 있으므로, 마지막을 제외하고서는 M권을 가져다 놓고 다시 0으로 돌아와야 합니다.

즉, 단 한번은 편도로 이동이 가능합니다. 최소로 걸음하기 위해서 이 편도를 가장 먼 거리로 사용해야 합니다. 따라서, 절대값이 가장 큰 값을 마지막으로 하여, 가장 먼 곳에서 끝내고 돌아오지 않는 경우가 최소로 걸음하는 경우입니다.

나머지의 경우는 왕복으로 이동해야 하므로, 각 걸음마다 가장 먼 거리 * 2 만큼 걸음합니다. 즉, 매 순간 최선의 선택인 최대한 먼 곳에 가서 M권을 모두 처리하고 돌아오는 방식을 택합니다.

만약 먼 곳부터 처리하지 않으면, 멀리 두 번 가야하는 비효율이 생깁니다. 또 한 번에 최대한 많이 책을 가져다 놓아야 왕복 횟수를 최소화해서 거리를 최소화할 수 있습니다. 이 두 가지 선택 조건이 최선의 판단이고 이러한 전략이 그리드입니다.

이에 따라 구현해보겠습니다.

우선, 그리디를 위한 전처리로 거리 순으로 위치를 정렬해야 합니다. 책 위치를 음수값과 양수값으로 나눕니다. 이유는 입력 예를 들어 설명하겠습니다.

// 우선 위치를 오름차순으로 정렬해 보겠습니다. [-39, -37, -29, -28, -6, 2, 11]
const locations = input[1].split(' ').map(Number).sort((a, b) => a - b);

가장 먼 거리의 편도 처리를 생각하지 않고, 위치 순서대로 다녀오면 다음과 같습니다.

위치를 오름차순으로 정렬해서 2권씩 놓고 온다고 했을 때, -6 부분에서는 2권을 가져다 놓을 수 없습니다. 다음 책 위치인 2 는 양수로 바뀌므로 0을 지나 2를 새로 가야합니다. 이를 고려하기 위해 위치를 음수값과 양수값으로 나누어 생각합니다.

이 때, 음수는 오름차순으로, 양수는 내림차순으로 정렬해야 가장 먼 걸음 순으로 정렬됩니다.

const locations = input[1].split(' ').map(Number);

// 음수/양수 위치로 나누고 정렬
const negativeBooks = locations.filter(x => x < 0).sort((a, b) => a - b);      // 작은 순서: [-39, -37, -29, -28, -6]
const positiveBooks = locations.filter(x => x > 0).sort((a, b) => b - a);      // 큰 순서: [11, 2]

그리고 이제 각각을 반복문으로 돌면서 가장 먼 거리부터 M권씩 가져다 놓으며 걸음 수를 세어줍니다.(그리디 전략)

const distances = [];

// 각 방향에서 M권씩 묶어 가장 멀리 있는 거리만 기록
for (let i = 0; i < negativeBooks.length; i += M) {
  distances.push(Math.abs(negativeBooks[i]));
}
for (let i = 0; i < positiveBooks.length; i += M) {
  distances.push(positiveBooks[i]);
}

걸음 수의 배열에서 가장 먼 거리만 편도로 이동하고 나머지는 왕복으로 이동하도록 처리합니다.

const farthest = Math.max(...distances);
// 전부 2를 곱해서 왕복으로 처리하고 max값을 빼서 편도로 처리합니다.
const totalDistance = distances.reduce((sum, d) => sum + d * 2, 0) - farthest;

refactor

다 적고 보니 거리 누적을 따로 계산할 필요가 없어 보입니다. 바로바로 계산하도록 리팩토링해 보겠습니다.

let totalDistance = 0;
let farthest = 0;

for (let i = 0; i < negativeBooks.length; i += M) {
  const distance = Math.abs(negativeBooks[i]);
  totalDistance += distance * 2;
  // 거리를 계산하면서 비교하여 최댓값도 찾습니다.
  if (distance > farthest) farthest = distance;
}

for (let i = 0; i < positiveBooks.length; i += M) {
  const distance = positiveBooks[i];
  totalDistance += distance * 2;
  // 거리를 계산하면서 비교하여 최댓값도 찾습니다.
  if (distance > farthest) farthest = distance;
}

// 가장 먼 거리 값은 편도로 처리하기 위해 한 번 뺴줍니다.
totalDistance -= farthest;

console.log(totalDistance);

성능상 이점은 없지만, 리팩토링으로 좀 더 코드가 간결해졌습니다.

최종 코드

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

const [N, M] = input[0].split(' ').map(Number);
const locations = input[1].split(' ').map(Number);

const negativeBooks = locations.filter(x => x < 0).sort((a, b) => a - b);      // 왼쪽 책: 작은 순서
const positiveBooks = locations.filter(x => x > 0).sort((a, b) => b - a);      // 오른쪽 책: 큰 순서

let totalDistance = 0;
let farthest = 0;

for (let i = 0; i < negativeBooks.length; i += M) {
  const distance = Math.abs(negativeBooks[i]);
  totalDistance += distance * 2;
  if (distance > farthest) farthest = distance;
}

for (let i = 0; i < positiveBooks.length; i += M) {
  const distance = positiveBooks[i];
  totalDistance += distance * 2;
  if (distance > farthest) farthest = distance;
}

totalDistance -= farthest;

console.log(totalDistance);