[백준] 1253 좋다 (Javascript)

문제

BOJ1253_좋다

풀이

첫 번째 발상

처음에는 가장 단순한 방법으로, 3중 for문을 돌리는 방법을 떠올렸으나 N=2000이고 3중 for문의 시간복잡도는 $O(N^3)$이므로 탈락

두 번째 발상

객체와 2중 for문을 이용해서 obj[arr[i]+arr[j]]=true 을 수행한 뒤, for문을 한번 더 실행해서 obj[arr[i]]가 true 라면 arr[i]를 만들 수 있는 경우가 존재하는 것이기 때문에 카운트를 1증가시키는 방식으로 하려고 했다.

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 arr = input[1].split(' ').map(Number);
const sum = {};
for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
        if (i === j) continue;
        sum[arr[i] + arr[j]] = true;
    }
}

let answer = 0;
for (let i = 0; i < N; i++) {
    if (sum[arr[i]]) answer++;
}
console.log(answer);

이렇게 하면 시간복잡도는 $O(N^2+N) = O(N^2)$ 이므로 시간초과는 나지 않는다.

하지만 아래와 같은 반례가 존재했다.

3
0 0 3

correct answer: 0
wrong answer: 1

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

세 번째 발상

결국 다른 분들의 코드를 보고, 투 포인터를 이용해서 풀었다.

기존의 이진 탐색과 다른 점은 이진 탐색은 매 탐색마다 범위를 절반씩 줄여나가기 때문에 $O(\log N)$이었다면, 이 문제에서는 범위를 반 씩 줄여나가는 게 아니라 left+1 혹은 right-1 씩 범위를 줄여나가기 때문에 탐색에 $O(N)$의 시간이 든다.

이걸 N번 반복하니 총 시간복잡도는 $O(N^2)$이 된다.

코드

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 arr = input[1]
    .split(' ')
    .map(Number)
    .sort((a, b) => a - b);
let answer = 0;

for (let i = 0; i < N; i++) {
    answer += towPointer(i);
}
console.log(answer);

function towPointer(target) {
    let left = 0;
    let right = N - 1;
    while (left < right) {
        const sum = arr[left] + arr[right];
        if (sum === arr[target]) {
            // target이 sum에 포함되면 안됨
            if (left === target) left++;
            else if (right === target) right--;
            else return 1;
        } else if (sum > arr[target]) right--;
        else left++;
    }
    return 0;
}