[백준] 3273

두 수의 합

문제

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)

출력

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

풀이

const sum = () => {
  const fs = require("fs");
  let input = fs.readFileSync("/dev/stdin").toString().trim().split("\\n");
  const arr = input[1].split(" ").map((n) => {
    return parseInt(n);
  });
  const sum = parseInt(input[2]);
  let arrAvailable = [];
  let ret = 0;

  for (let i = 0; i < 2000001; i++) {
    arrAvailable.push(false);
  }
  for (let i = 0; i < arr.length; i++) {
    if (sum - arr[i] > 0 && arrAvailable[sum - arr[i]]) ret++;
    arrAvailable[arr[i]] = true;
  }
  console.log(ret);
};

sum();

반성회

메모리 제한에 계속 걸린 문제

처음에는 원본 배열 (arr) 을 현재 원소 기준으로 slice해서 find 메소드로 원소를 찾는 방법을 사용했었는데, find가 내부에서 함수를 돌려서 찾는 거라 그런지 아니면 slice 때문인지 메모리 초과가 났다

방법은 boolean 배열 하나를 최대 n의 개수만큼 선언해서 해당 숫자가 앞에서 등장했는지 여부를 true, false로 저장하는 것

배열의 접근 시간복잡도는 O(1) 이기 때문에 원소가 배열에 등장했는지 알아보기 위해 bool 배열을 사용하면 메모리와 시간을 아껴 빠르게 원소 존재여부를 찾을 수 있다