[백준 2470 - Node.js] 두 용액

🔗 문제 링크

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

2470번: 두 용액

✏️ 풀이

const [N, input] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

const solutions = input
  .split(' ')
  .map(Number)
  .sort((a, b) => a - b);

let i = 0;
let j = N - 1;
let minValue = Infinity;
const twoSolutions = [i, j];

while (i < j) {
  const sum = solutions[i] + solutions[j];
  const curValue = Math.abs(sum);

  if (minValue > curValue) {
    minValue = curValue;
    twoSolutions[0] = i;
    twoSolutions[1] = j;
  }
  
  if (sum < 0) {
    i++;
  } else {
    j--;
  }
}

console.log(twoSolutions.map(i => solutions[i]).join(' '));

용액들을 특성값을 기준으로 오름차순한 후에 투 포인터를 맨 앞과 맨 끝부터 시작해서 두 용액의 특성값의 합이 0에 가장 가까운 용액의 쌍을 찾으면 된다.

 

현재 선택한 두 용액의 특성값의 합을 구한 후, 그 절댓값이 minValue보다 작다면 minValue와 그 minValue를 만드는 두 용액의 index를 저장하는 twoSolutions를 갱신한다. 그리고 두 용액의 특성값의 합이 음수면 왼쪽 인덱스를 증가시키고, 양수면 오른쪽 인덱스를 증가시켜서 그 합이 점점 0에 더 가깝도록 한다. 이 과정을 i < j인 동안 반복하면 O(n) 시간에 정답을 구할 수 있다.