[백준] Node.js / 2470 - 두 용액 (투 포인터)

투 포인터(Two Pointers) 알고리즘

2470번: 두 용액

 

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

 

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

 

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

 

예제 입력 1

5
-2 4 -99 -1 98

 

예제 출력 1

-99 98

 

나의 풀이

이전에 풀었던 백준 두 수의 합 문제와 푸는 방식은 비슷했다.

[백준] Node.js / 3273 - 두 수의 합 (투 포인터)

 

1. 먼저 오름차순으로 정렬 해준 뒤, 조건문을 통해 두 용액의 합의 절댓값이 작은 값을 구한다.
2. 투 포인터의 이동 
   • 만약 두 용액의 합이 음수면 0으로 가까이 가기 위해서는 더 큰 값을 더해줘야 하므로, start++해준다.
   • 양수면 더 작은 값을 더해줘야 하므로 end-- 해준다.

 

나는 투 포인터의 이동 코드를 잘못 생각해냈다. 단순히 0에 가까운 값을 구하면 바로 start++을 해줬는데, 이는 '두 수의 합의 절댓값이 0에 가까워야 한다'는 조건을 고려하지 못해서 그렇게 단순히 생각했었다.

 

코드

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const N = Number(input[0]);
const arr = input[1]
  .split(" ")
  .map((x) => Number(x))
  .sort((a, b) => a - b);

let start = 0;
let end = N - 1;
let minSum = Number.MAX_SAFE_INTEGER;
let answer = [null, null];

while (start !== end) {
  if (Math.abs(arr[start] + arr[end]) < minSum) {
    minSum = Math.abs(arr[start] + arr[end]);
    answer[0] = arr[start];
    answer[1] = arr[end];
  }

  if (arr[start] + arr[end] < 0) {
    start++;
  } else {
    end--;
  }
}

console.log(...answer);