[BaekJoon] 1744번 수 묶기_JavaScript

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

1744번: 수 묶기

---

Question

 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

Input

 첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

Output

 수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

---

Example Input

4
-1
2
1
3

Example Output

6

---

My Solutions

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((val) => +val);

const [n, ...list] = input;

function solution(n, list) {
  const minusArr = [];
  const plusArr = [];
  let zeroCnt = 0;
  let oneCnt = 0;
  let ans = 0;

  for (let i = 0; i < n; i++) {
    if (list[i] === 0) {
      zeroCnt++;
    } else if (list[i] === 1) {
      oneCnt++;
    } else if (list[i] < 0) {
      minusArr.push(list[i]);
    } else {
      plusArr.push(list[i]);
    }
  }

  const sortedMinus = minusArr.sort((a, b) => b - a);
  const sortedPlus = plusArr.sort((a, b) => a - b);

  while (sortedPlus.length > 1) {
    const first = sortedPlus.pop();
    const second = sortedPlus.pop();

    ans += first * second;
  }

  if (sortedPlus.length % 2 === 1) {
    ans += sortedPlus.pop();
  }

  while (sortedMinus.length > 1) {
    const first = sortedMinus.pop();
    const second = sortedMinus.pop();

    ans += first * second;
  }

  if (sortedMinus.length % 2 === 1 && zeroCnt === 0) {
    ans += sortedMinus.pop();
  }

  ans += oneCnt;

  console.log(ans);
}

solution(n, list);

---

 처음엔 1715번 문제와 같이 heap을 사용해서 풀어야 하는 문제인 줄 알고 헤맸는데 pop() 메서드를 활용하면 생각보다 간단히 풀리는 문제였다.

 

 주어진 숫자에서 가능한 큰 수끼리 묶어야 결괏값이 커진다는 사실에 주목하자. -1 * 3 + 1 * 2 보다 -1 * 1 + 2 * 3이 결괏값이 더 크다. 또한 음수끼리 곱하면 양수로 변하는 성질도 활용하여 문제를 풀어보자.

 

1.  우선 주어진 수열을 음수, 1보다 큰 수, 0, 1 4가지로 나누어 빈 배열에 저장한다.
2. 1보다 큰 수를 담은 배열을 정렬해 최댓값과 그 다음으로 큰 값을 곱한 후 더해나간다. 원소의 개수가 홀수일 때는 마지막 남은 수를 그대로 더 한다.
3. 음수를 담은 배열을 정렬해 최솟값과 그 다음으로 작은 값을 곱한 후 더해나간다. 원소의 개수가 홀수일 때는 수열에 0이 있다면 1개 남는 음수를 0과 곱해 0으로 만들고, 0이 없다면 그대로 더한다.

 

 위 과정을 통해 구한 값을 누적하여 더하고, 그 값에 1의 개수를 더한다.

---

함께 보기

1. pop() 메서드

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/pop

Array.prototype.pop() - JavaScript | MDN