[백준1253_자바스크립트(javascript)] - 좋다

🔴 문제

좋다

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(BigInt));
const n = Number(inputs[0][0]);
const A = inputs[1];

const map = new Map();

for (const a of A) {
  if (map.has(a)) map.set(a, map.get(a) + 1);
  else map.set(a, 1);
}

let ans = 0;
const bt = (selected, start) => {
  if (selected.length === 2) {
    const sum = selected[0] + selected[1];

    if (map.has(sum)) {
      if (sum === selected[0] && sum === selected[1] && map.get(sum) === 2)
        return;
      if (sum === selected[0] && map.get(sum) === 1) return;
      if (sum === selected[1] && map.get(sum) === 1) return;
      ans += map.get(sum);
      map.delete(sum);
    }
    return;
  }

  for (let i = start; i < n; i++) {
    bt([...selected, A[i]], i + 1);
  }
};

bt([], 0);

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

풀이 방식은 모든 좋은 수를 고르고, 이 좋은수가 수열안에 몇 개 있는지 세어준다.
즉 맵으로 숫자 체크를 하고 백트래킹으로 좋은 수를 고르자!로 풀이했다.
좋은 수가 수열안에 몇 개 있는지 세기 위해서 모든 자들이 몇 번 나왔는 지를 체크해주는 맵을 만들었다.

for (const a of A) {
  if (map.has(a)) map.set(a, map.get(a) + 1);
  else map.set(a, 1);
}

그 후 모든 좋은 수를 백트래킹으로 골랐다.
백트래킹 함수는 좋은 수를 배열로 관리하는 selected, 탐색의 시작을 관리하는 start변수를 매개변수로 받는다.
같은 위치의 수를 두 번 이상 뽑을 수 없고, 두 수를 뽑는 행위는 순열이 아는 조합이기 때문에 반복문은 start부터 n까지 순회하며 재귀호출 한다. 이 때 selected를 업데이트 해주고 시작위치 또한 업데이트해준다.
만약 두 개의 수가 뽑혔으면, 두 수를 더해주고, 만약 map 객체에 sum이 있다면 좋은 수 체크를 해주고 없다면 재귀호출을 종료한다.
이 때 체크해줘야할 점은 0 0 1, 0 1 1 이렇게 0이 뽑혔을 경우다.
좋은 수를 체크할 때는 두 개의 수를 더한 값이 자기 자신과 달라야 한다. 하지만 0을 고르는 경우 예외처리를 하지 않으면 0 + 1를 했을 때 자기자신 1을 고르는 경우가 생긴다. 0+0도 마찬가지 이므로 해당 경우를 예외처리 해주고, 이 조건에 걸리지 않는다면, 즉 유효하다면 sum을 키 값으로 가진 벨류를 ans에 더해준다. 이 때 한 번 더한 수는 이미 좋은수라고 판별이 되었기 때문에 더 이상 ans에 계산되면 안된다. 따라서 map에서 제거한다.

근데 이 방법은 결국 모든 경우의 수를 탐색해주기 때문에 효율성이 좋지 않다.

• 위는 백트래킹, 아래는 이분탐색으로 풀이 6배 가량의 시간차이
  

따라서 이분탐색으로 풀이하는 것이 옳을 듯 하다.

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs.readFileSync(path, 'utf-8').trim().split('\r\n');

const n = Number(inputs[0]);
const A = inputs[1]
  .split(' ')
  .map(Number)
  .sort((a, b) => a - b);

function isGood(target) {
  let left = 0;
  let right = A.length - 1;

  while (left < right) {
    const sum = A[left] + A[right];

    if (left === target) {
      left += 1;
      continue;
    } else if (right === target) {
      right -= 1;
      continue;
    }

    if (sum === A[target]) return true;
    else if (sum < A[target]) left += 1;
    else right -= 1;
  }

  return false;
}

let ans = 0;
for (let i = 0; i < A.length; i++) {
  if (isGood(i)) ans += 1;
}

console.log(ans);

이분탐색을 위해 A배열을 정렬하고 A배열의 모든요소를 돌면서 두 수를 더했을 때 내가 되는 경우 가 있는지 체크해주는 로직이다 두 수를 선택하는 과정을 투 포인터로 구현했다.

🔵 Ref