백준 / 투 포인터 / 2470번 / 두 용액 / JS

< 문제 바로가기 >

2470번: 두 용액

 

/* 두 용액 */
const fs = require('fs');
// const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

const N = +input.shift();
const valueList = input.shift().split(' ').map(Number);

function solution(N, valueList) {
  let sortedValueList = valueList.sort((a, b) => a - b);
  let [start, end] = [0, N - 1];

  let [value1, value2] = [0, 0];
  let result = [];
  let min = Infinity;
  while(start < end) {
    [value1, value2] = [sortedValueList[start], sortedValueList[end]];

    if(value1 + value2 === 0) {
      result = [value1, value2];
      break;
    }
    if(Math.abs(value1 + value2) < min) {
      min = Math.abs(value1 + value2);
      result = [value1, value2];
    }

    if(value1 + value2 < 0) {
      start += 1;
    }
    else {
      end -= 1;
    }
  }

  result = result.sort((a, b) => a - b).join(' ');
  console.log(result);
}

solution(N, valueList);

---

정렬한 후, 맨 처음부터 증가하는 포인터 하나와 맨 끝 부터 감소하는 포인터 하나로 풀면 되는 문제이다.

두 포인터가 가리키는 값의 합이 0에 가까울수록 정답에 근접해지므로, 현재 저장되어있는 합보다 더 0에 가까운 수이면 값을 갱신해주어야 한다. 이 과정은 절댓값을 이용해서 양수, 음수 상관없이 제일 작은 값을 저장해주면 된다.

 

그리고 현재 두 합이 음수라면 오름차순으로 정렬이 되어있으므로 start 포인터를 증가시켜 값을 증가시켜주면 되고, 현재 두 합이 양수라면 end 포인터를 감소시켜 값을 감소시켜주면 된다.