[JavaScript] 백준 3273번 두 수의 합

이 글은 백준 3273번 두 수의 합을 풀이한다. 코드는 JavaScript로 구현하였다.

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

예제 입력 1

9
5 12 7 10 9 1 2 3 11
13

예제 출력 1

3

제한

• 시간: 1초
• 메모리: 128MB

풀이

접근

이 문제는 입력으로 주어진 수열과 자연수 X를 이용하여 조건을 만족하는 쌍의 개수를 구하는 문제이다.

처음에는 완전탐색을 이용해서 이 문제를 풀려고 했다가, 시간초과가 났다.

완전 탐색으로 진행한다면 각 위치 N에 대해 이전의 경우의 수를 모두 따져봐야 하니 2중 반복문에 의해 O(N^2)의 시간복잡도를 갖게 된다. 

그렇다면, N이 최대 100,000이므로 주어진 시간 이내에 풀어낼 수가 없다.

 

그래서 생각해낸 방법이 입력값을 오름차순으로 정렬하여 비교하고, 끝 값부터 차례대로 비교하면서 필요한 경우에만 인덱스를 조정하여 쌍의 개수를 구하는 것이였다.

 

인덱스를 조정하는 로직은 다음과 같다.

- 두 수의 합이 X와 같으면 count를 증가시키고, i와 j를 각각 증가시키고 감소시킨다.
- 두 수의 합이 X보다 작으면 i를 증가시킨다.
- 두 수의 합이 X보다 크면 j를 감소시킨다.

 

이러한 방식을 투 포인터 알고리즘(Two-Pointers Algorithm)이라고 한다.

구현

내가 구현한 코드

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 arr = input[1]
  .split(" ")
  .map(Number)
  .sort((a, b) => a - b);
const X = Number(input[2]);

// 변수 선언
let count = 0;
let i = 0; // 배열 시작 인덱스
let j = N - 1; // 배열 끝 인덱스

// 끝 값부터 차례대로 비교
while (i < j) {
  const sum = arr[i] + arr[j];
  // sum == X일 시, i와 j 둘다 증감
  if (sum == X) {
    count++;
    i++;
    j--;
  } else if (sum < X) {
    i++;
  } else {
    j--;
  }
}

// 쌍의 개수 출력
console.log(count);

성능 비교