[백준1461_자바스크립트(javascript)] - 도서관

🔴 문제

도서관

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs.readFileSync(path, 'utf-8').toString().trim().split('\n');

const [n, m] = inputs[0].split(' ').map(Number);
const books = inputs[1].split(' ').map(Number);

const left = books
  .filter((it) => it < 0)
  .map((it) => -1 * it)
  .sort((a, b) => b - a);
const right = books.filter((it) => it > 0).sort((a, b) => b - a);

let ans = 0;

for (let i = 0; i < left.length; i += m) {
  ans += left[i] * 2;
}

for (let i = 0; i < right.length; i += m) {
  ans += right[i] * 2;
}

if (left.length === 0) ans -= right[0];
else if (right.length === 0) ans -= left[0];
else if (left.length && right.length) {
  if (left[0] > right[0]) ans -= left[0];
  else ans -= right[0];
}
console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

그리디 알고리즘
첫번째 테스트 케이스에서 정답을 찾다보니, 책의 좌표를 음수와 양수로 나누어서 m권씩 묶으면 된다는 결론이 나왔다.
그래서 내 위치보다 왼쪽은 즉 음수인 책과 양수인 책을 나누어 각각 left와 right에 저장해주었다. 이때 left는 -1을 곱해 양수로 변경해주었다. 그 후 내림차순으로 각 배열을 정렳해주었다.
left 배열과 right 배열을 순회할텐데 for문의 세번째 요소에 i += m을 넣어 m단위로 순회할 수 있도록 했다.
문제의 마지막 조건데 책을 가져다 놓은 뒤에 다시 0으로 돌아올 필요가 없다 이므로 절대값이 가장 큰 요소를 마지막에 빼주는 것이 최소 이동거리가 나온다.
따라서 left의 길이가 0 이라면 right의 첫 요소를 빼줘야 하고, right의 길이가 0이라면 left의 첫 요소를에 빼줘야 한다.
두 배열의 길이가 모두 0 이상이라면 두 배열의 첫 요소를 비교해서 더 큰 요소를 빼주는 것이 최소 이동 거리이다.

🔵 Ref