[백준] 2473 - 세 용액 (Javascript)

문제 설명 : https://www.acmicpc.net/problem/2473

 

 

문제 요약 :

1. 세 개의 용액의 합의 절댓값이 0에 가까운 용액 집합 찾기

 

문제 풀이 시간 : 2시간

문제 성공 여부 : 실패

 

 

접근 방법(실패) :

1. 2개 용액의 합 리스트(twoSum) 만들기
2. n개의 정렬된 용액 이분탐색
3. 세 가지의 용액의 합의 절대값이 최소인 집합 찾기

 

해당 방법의 최악의 경우는 다음과 같다.

 

1. twoSum의 개수 : 5000 * 4999 / 2 = 12497500

2. N 이분탐색 횟수 : log2(5000) = 약 13

 

두 계산의 합은 약 1.6억이기 때문에 제한시간인 1초 내에 해결이 불가능하였다.

 

 

접근 방법(성공) :

1. 한 가지 용액을 고정(i)하고 해당 인덱스의 왼쪽(left)과 오른쪽(right) 끝의 투 포인터를 사용한다.
2. left, i, right 인덱스의 용액의 합을 구한다
3. 0보다 작을경우 left++
4. 0보다 클 경우 right-- 를 한다.

이 경우, N개에 대해서 각각 left right를 i에 도달할 때까지 탐색하기 때문에 O(N)의 시간복잡도가 계산된다.

따라서, 5000 * 5000 = 25,000,000 이므로 문제 해결이 가능하다.

 

알고 보니 굉장히 쉬운 문제였는데 미처 투 포인터만으로 해결할 생각을 못했던 것 같아 아쉽다.

 

전체 코드(성공) :

const solution = () => {
  const fs = require("fs");
  const filePath = process.platform === "linux" ? "dev/stdin" : "input.txt";
  const input = fs.readFileSync(filePath).toString().split("\n");
  const N = Number(input[0]);
  const water = input[1].split(" ").map(Number);

  water.sort((a, b) => a - b);
  let min = Number.MAX_VALUE;
  let ans = [0, 0, 0];
  for (let i = 1; i < N - 1; i++) {
    let left = 0;
    let right = N - 1;

    while (left < i && i < right) {
      const sum = water[left] + water[i] + water[right];
      const abs = Math.abs(sum);
      if (abs < min) {
        min = abs;
        ans = [water[left], water[i], water[right]];
      }

      if (sum < 0) {
        left++;
      } else if (sum > 0) {
        right--;
      } else {
        break;
      }
    }
  }

  return ans.join(" ");
};

const answer = solution();
console.log(answer);