[백준] 1744 수 묶기 - javascript

📌 문제

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

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let n = Number(input[0]);
let plus_arr = [];
let minus_arr = [];
let ans = 0;
let has_zero = false;
for (let i = 0; i < n; i++) {
  if (Number(input[i + 1]) === 1) {
    ans++;
  } else if (Number(input[i + 1]) === 0) {
    has_zero = true;
  } else if (Number(input[i + 1]) < 0) {
    minus_arr.push(Number(input[i + 1]));
  } else {
    plus_arr.push(Number(input[i + 1]));
  }
}

plus_arr.sort((a, b) => b - a);
minus_arr.sort((a, b) => a - b);

if (has_zero && minus_arr.length % 2 === 1) {
  minus_arr.pop();
}
if (plus_arr.length % 2 === 1) {
  ans += plus_arr[plus_arr.length - 1];
  plus_arr.pop();
}
if (minus_arr.length % 2 === 1) {
  ans += minus_arr[minus_arr.length - 1];
  minus_arr.pop();
}

for (let i = 0; i < plus_arr.length; i += 2) {
  ans += plus_arr[i] * plus_arr[i + 1];
}
for (let i = 0; i < minus_arr.length; i += 2) {
  ans += minus_arr[i] * minus_arr[i + 1];
}

console.log(ans);

✔ 알고리즘 : 그리디

✔ 우선 수열의 수를 받을 때 경우의 수를 4가지로 나누었다.

• 1이 들어올 때
  1은 모든 다른 수와 곱했을 때 더하는 값보다 작아지게 된다. 따라서 무조건 더해야 하는 수이므로 ans에 바로 1을 더해주었다.
• 0이 들어올 때
  0은 더해도 0이다. 하지만 음수와 곱해졌을 때는 0으로 값이 작아지게 된다. 하지만 음수의 개수가 짝수인 경우에는 음수끼리 곱하는 것이 전체 합이 커지기 때문에 후에 판단하기 위해 has_zero라는 boolean 변수를 true로 바꿔준다.
• 음수가 들어올 때
  음수 배열인 minus_arr에 push 해준다.
• 양수가 들어올 때
  양수 배열인 plus_arr에 push 해준다.

✔ 양수배열은 내림차순, 음수배열은 오름차순으로 정렬해준다.

✔ 수열에 0값이 존재하고 음수배열의 길이가 홀수인 경우 제일 큰 음수(0에서 제일 가까운 음수)를 제거해야하므로 minus_arr에서 pop을 해준다.

✔ 양수와 음수배열의 길이가 홀수인 경우 양수의 경우 제일 작은 양수, 음수의 경우 제일 큰 음수(0에서 제일 가까운 음수)를 제거해야하므로 pop을 해준다.

✔ 최종적으로 양수와 음수배열에 남은 원소수는 짝수개이다. 순차적으로 곱해서 ans에 더해준다.

✔ 난이도 : 백준 기준 골드 4