문제 개요

문제: 수 묶기

분류: 그리디 알고리즘, 정렬, 많은 조건 분기

난이도: 골드4

문제 풀이

수열의 각 수를 묶을 때 그 합이 최대가 되게 하기 위해서는

1. 양수는 큰 수부터 차례대로 두 개씩 묶는다.
   단, 1의 경우는 묶지 않고 그대로 더한다.
   • ex) 3, 5, 7, 9가 있을 때 35+79가 최댓값이 된다.
   • ex) 1, 2, 3, 4가 있을 때 12+34보다 1+2+3*4가 더 크다.
2. 음수는 작은 수부터 차례대로 두 개씩 묶는다.
   • ex) -6, -3, -2, -1이 있을 때 (-6)(-3)+(-2)(-1)이 최댓값이 된다.
3. 0은 가장 큰 음수와 묶거나 자기 자신과 묶는다.

따라서 주어진 수를 양수, 음수로 나누어 새로운 배열에 저장하고 양수는 내림차순, 음수는 오름차순으로 정렬하여 앞에서부터 2개씩 곱하여 누적 합한다.
또한 0은 존재 여부만 체크하여 존재한다면 음수가 홀수개인 경우 가장 큰 음수와 곱하면 된다.

양수, 음수가 홀수개인 경우 각각 편리한 계산을 위해 아래의 과정을 수행한다.

1. 양수 배열의 길이가 홀수인 경우, 배열에 1을 추가한다.
   • ex) 8, 5, 3, 3, 2가 있을 때 2=2*1이므로 1을 추가한다.
2. 음수 배열의 길이가 홀수인 경우, 수열에 0이 존재한다면 0, 존재하지 않는다면 1을 추가한다.
   • ex) -5, -3, -1이 있을 때 수열에 0이 존재한다면 0을 추가하여 최댓값(15)을 만든다. 반대로 0이 존재하지 않는다면 1을 추가한다.(14)

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let [N, ...numbers] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map(Number);

const solution = (N, numbers) => {
  let answer = 0;
  const negative = [];
  const positive = [];
  let isThereZero = false;

  numbers.forEach((num) => {
    if (num === 1) answer++;
    else if (num < 0) negative.push(num);
    else if (num > 0) positive.push(num);
    else if (num === 0) isThereZero = true;
  });

  negative.sort((a, b) => a - b);
  positive.sort((a, b) => b - a);

  if (negative.length % 2 === 1) negative.push(isThereZero ? 0 : 1);
  if (positive.length % 2 === 1) positive.push(1);

  for (let i = 0; i < negative.length - 1; i += 2)
    answer += negative[i] * negative[i + 1];
  for (let i = 0; i < positive.length - 1; i += 2)
    answer += positive[i] * positive[i + 1];

  console.log(answer);
};

solution(N, numbers);