백준 1461 도서관 js

1461번: 도서관

문제 설명

단순 정렬 문제입니다.

 

풀이.

중요한 포인트는 마지막으로 책을 놔두고 다시 0으로 돌아올 필요가 없다는 것 입니다.

따라서 마지막으로 두어야 할 책은 가장 먼 위치의 책입니다.

 

1. 책의 원래 위치가 0이 아닌 정수이므로 우선 위치가 음수인 배열과 양수인 배열로 나누어주고, 내림차순으로 정렬해 주었습니다.

 

2. 다시 0으로 돌아올 필요가 없는 가장 먼 위치의 책을 놔두는 경우를 먼저 제거해 줍니다.

양수의 배열과 음수의 배열을 절댓값으로 치환했을 때 더 큰 수가 존재하는 배열의 가장 큰 수를 정답에 더해주고, 큰 수 순으로 M개의 수를 배열에서 제거해 줍니다.

 

자 이제 가장 비용이 많이 드는 경우를 마지막으로 둔다고 가정하고 2번에서 제거해 주었으니, 나머지 책은 제자리에 두고 0으로 돌아와야 합니다. 가장 먼 위치에 존재하는 책의 거리 x 2를 정답에 더해주고, M개씩 책을 제거해주면 됩니다.

 

3. 양수의 배열과 음수의 배열 따로 M개씩 책을 제자리에 두고, 거리(왕복)만큼 정답에 더하여 정답을 구해줍니다.

 

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

let N, M;

rl.on("line", function (line) {
  if (!N) {
    [N, M] = line.split(" ").map(Number);
  } else {
    let result = 0;
    const input = line.split(" ").map(Number);

    let positive = []; // 양수에 위치하는 책들
    let negative = []; // 음수에 위치하는 책들

    // 1. 양수, 음수 배열을 따로 나누고, 절댓값으로 치환.
    input.forEach((n) => {
      if (n > 0) {
        positive.push(n);
      } else {
        negative.push(Math.abs(n));
      }
    });

    // 1. 내림차순 정렬
    positive.sort((a, b) => b - a);
    negative.sort((a, b) => b - a);
    
    // 2. 양수의 배열과 음수의 배열 더 큰 수가 존재하는 배열은 
    // 가장 큰 수를 정답에 더해주고, M개의 수 만큼 제거.
    if (positive.length === 0 || positive[0] < negative[0]) {
      result += negative[0];
      negative = negative.slice(M);
    } else {
      result += positive[0];
      positive = positive.slice(M);
    }
    
    // 3. M개의 책씩 제자리에 두고, 가장 먼 위치의 거리(왕복)만큼
    // 정답에 더하여줍니다.
    let index = 0;
    while (index < negative.length) {
      result += negative[index] * 2;
      index += M;
    }
    index = 0;
    while (index < positive.length) {
      result += positive[index] * 2;
      index += M;
    }
    console.log(result);
    rl.close();
  }
});