[백준] 2295 세 수의 합 (Javascript)

잭슨·2024년 5월 10일

백준 알고리즘 이진탐색 자바스크립트

알고리즘 문제 풀이

목록 보기

90/130

문제

BOJ2295_세 수의 합

풀이

요구사항

N개의 자연수 집합이 있다.
이 중 세 가지 수를 더했을 때 그 합이 집합에 있는 자연수 중 하나와 일치해야 한다.
그리고 그 중 가장 큰 수를 출력하라.
집합 내에 중복되는 수는 없으며, 같은 수를 반복해서 더해도 된다.

해결방안

처음엔 3중 for문을 돌려서 모든 경우의 세 가지 수를 합했을 때의 합을 배열에 저장한뒤, 집합과 비교하여 최댓값을 구할까 생각했는데, 3중 for문을 돌리는 시점에서 이미 $O(N^3)$ 이기 때문에 시간초과가 난다.

따라서 다른 방법을 찾아봐야 했다.

이진탐색

결국 다른 분들의 코드를 확인했다.
풀이는 이러했다.
x+y+z = k 라고 했을 때, x+y = k-z 라고 볼 수도 있다.

x+y+z 의 모든 경우를 구하기 위해선 $O(N^3)$ 의 시간이 걸리지만 x+y를 구하기 위해선 $O(N^2)$ 의 시간밖에 안 걸린다.

따라서 먼저 x+y를 전부 구해서 sum이라는 배열에 저장한 다음, k-z를 전부 구하며 sum 배열에 k-z 와 동일한 값이 있다면, x+y+z로 k를 만들 수 있는 것이다.

배열에 k-z와 동일한 값이 있는지 확인할 때는 이진 탐색을 사용해 탐색에 걸리는 시간을 $O(N^2 * logN)$ 으로 줄여준다. 만약 순차 탐색을 수행할 경우 시간 복잡도는 $O(N^3)$ 이 되므로 시간초과가 뜬다.

또한 최대값만 출력해주면 되므로 집합 배열과, sum 배열을 오름차순 정렬 후 뒤에서부터 검사해준다. (또는 내림차순 정렬 후 앞에서부터 검사해준다.)

그런 다음 만약 x+y = k-z 가 성립한다면 그때의 k값을 출력하고 프로그램을 종료한다.

// x+y+z = k, x+y = k-z
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const union = input.slice(1).map(Number);
union.sort((a, b) => a - b);
const sum = [];

function binarySearch(left, right, target) {
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (sum[mid] === target) return true;
        else if (target < sum[mid]) right = mid - 1;
        else left = mid + 1;
    }
    return false;
}

for (let x = 0; x < N; x++) {
  // 중복을 최소화 하기 위해 y=x부터 시작
    for (let y = x; y < N; y++) {
        sum.push(union[x] + union[y]);
    }
}

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

for (let k = N - 1; k >= 0; k--) {
    for (let z = k; z >= 0; z--) {
        const target = union[k] - union[z];
        const exist = binarySearch(0, sum.length - 1, target);
        if (exist) {
            console.log(union[k]);
            process.exit();
        }
    }
}

z를 k부터 시작하는 이유는 union 배열은 오름차순 정렬되어 있기 때문에 z를 N-1부터 시작하면 z가 k보다 커지는 경우가 있기 때문에 target은 음수가 나올 수 있는데, sum에 저장된 값은 음수일 수 없기 때문에 음수가 나오는 경우는 고려할 필요 없어서다.

Set

Set 자료구조를 사용해서 푸는 방법도 있다.
푸는 원리는 이진탐색으로 푸는 방법과 동일하게 x+y = k-z 가 키 포인트지만 약간의 차이가 있다.

k-z값을 찾을 때, 이진 탐색을 수행하지 않고 Set.prototype.has메서드를 사용해서 확인한다.
Set 자료 구조는 내부적으로 해시 테이블( $O(1)$ )과 검색 트리( $O(logN)$ )와 같이 데이터를 조회하는 데에 걸리는 시간복잡도가 $O(N)$ 보다 좋게 설계되어 있기 때문에 오히려 이진 탐색보다 더 빠르게 동작한다.

명세서에서는 Set이 "평균적으로 컬렉션의 요소 수에 따라 선형 이하의 액세스 시간을 제공하는" 방식으로 구현되어야 한다고 요구하고 있습니다. 따라서 내부적으로 해시 테이블(O(1) 조회), 검색 트리(O(log(N)) 조회) 또는 복잡성이 O(N)보다 좋은 다른 데이터 구조로 표현할 수 있습니다.

출처: https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Set

따라서 아래와 같이 코드를 작성할 수 있다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const union = input.slice(1).map(Number);
union.sort((a, b) => b - a); // 내림차순 정렬
const sum = new Set();

for (let x = 0; x < N; x++) {
    for (let y = x; y < N; y++) {
        sum.add(union[x] + union[y]);
    }
}

for (const k of union) {
    for (const z of union) {
        if (sum.has(k - z)) {
            console.log(k);
            process.exit();
        }
    }
}