백준 2473 세 용액 js

 

2473번: 세 용액

풀이

두 용액을 먼저 선택하고 두 용액의 합한 값과 나머지 배열에서 하나의 값을 더했을 때 0에 가까운 값을 찾는 이분 탐색을 진행하였습니다.

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let N;
let input = [];
let min = 3000000000;

function solution() {
  let result = [];

  for(let i = 0; i < N - 2; i++) {
    for(let j = i + 1; j < N - 1; j++) {
      // 두 용액을 num1, num2로 지정
      let num1 = input[i];
      let num2 = input[j];
      
      // 나머지 배열인 j + 1 index부터 이분 탐색 시작
      let l = j + 1;
      let r = input.length - 1;

      while(l <= r) {
        let mid = (l + r) / 2 >> 0;
        let total = num1 + num2 + input[mid];

        if(min > Math.abs(total)) {
          min = Math.abs(total);
          result = [num1, num2, input[mid]];
        }

        if(total === 0) {
          return result;
        } else if(total > 0) {
          r = mid - 1;
        } else {
          l = mid + 1;
        }
      }
    }
  }

  return result;
}

rl.on('line', function (line) {
  if(!N) {
    N = +line;
  } else {
    input = line.split(' ').map(n => +n);
    input.sort((a, b) => a - b);
    
    let answer = solution()
    console.log(answer.join(' '));
    rl.close();
  }
})

위와 같이 단순하게 풀었더니 O(N^2logN)으로 그다지 효율적이지 않아 다른 사람들 코드를 참고하여 보았더니 하나의 값을 먼저 지정하고 나머지 두 개의 용액을 투 포인터 방식으로 총합이 0에 가까운 값을 찾는 솔루션이였습니다.

따라서 참고하여 O(N^2)의 시간 복잡도를 갖는 방식으로 수정해보겠습니다.

최종 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let N;
let input = [];
let min = 3000000000;

function solution() {
  let result = [];

  for(let i = 0; i < N - 2; i++) {
    let l = i + 1;
    let r = N - 1;

    while(l < r) {
      let total = input[i] + input[l] + input[r];

      if(min > Math.abs(total)) {
        min = Math.abs(total);
        result = [input[i], input[l], input[r]];
      }

      if(total > 0) {
        r -= 1;
      } else {
        l += 1;
      }
    }
  }

  return result;
}

rl.on('line', function (line) {
  if(!N) {
    N = +line;
  } else {
    input = line.split(' ').map(n => +n);
    input.sort((a, b) => a - b);
    
    let answer = solution()
    console.log(answer.join(' '));
    rl.close();
  }
})

오늘도 하나 배워갑니다.