문제 개요

문제: 세 수의 합

분류: 자료 구조, 이분 탐색, 해시를 사용한 집합과 맵, 중간에서 만나기

난이도: 골드4

문제 풀이

다른 사람 풀이를 참고했다.

세 개의 수를 고른다고 했으므로 우선 두 수의 합들을 구한다.

이후 (문제에서 세 수의 합이 가장 큰 경우를 구하라고 했으므로)집합의 가장 큰 수를 시작으로 하는 2중 반복문을 돌려서 어떤 수 a와 b의 차 c를 구하고, 이분탐색을 통해 두 수의 합들 중 c가 존재하는지 파악한다.

예를 들어 {1, 2, 3, 4, 11, 20}이라는 집합이 있다고 하자.
이 집합에서 구할 수 있는 두 수의 합은 {2, 3, 4, 5, 6, 7, 8, 12, 13, 14, 15, 21, 22, 23, 24, 31, 40}과 같다.

집합의 마지막 원소인 20부터 탐색을 시작하는데, 20-11을 했을 때 그 결과는 9가 된다. 하지만 두 수의 합 중에 9는 존재하지 않는다. 20-4, 20-3, 20-2, 20-1의 결과도 마찬가지이다.

다음 원소인 11로 넘어와서 11-4의 결과값인 6은 두 수의 합에 존재한다. 따라서 이 예제의 정답은 11이 된다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const binarySearch = (arr, data) => {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = ~~((left + right) / 2);

    if (arr[mid] === data) return true;
    else if (arr[mid] < data) left = mid + 1;
    else if (arr[mid] > data) right = mid - 1;
  }

  return false;
};

const solution = (input) => {
  const N = +input.shift();
  const U = input.map(Number);
  const sum = [];

  for (let i = 0; i < N; i++) {
    for (let j = i; j < N; j++) {
      sum.push(U[i] + U[j]);
    }
  }

  U.sort((a, b) => b - a);
  sum.sort((a, b) => a - b);

  for (let i = 0; i < N; i++) {
    for (let j = i; j < N; j++) {
      let temp = U[i] - U[j];
      if (binarySearch(sum, temp)) {
        console.log(U[i]);
        return;
      }
    }
  }
};

solution(input);