[boj] 1253. 좋다 (node.js)

문제 요약

[boj] 1253. 좋다 (node.js)

• 입력: N개의 숫자들
• 출력: 좋은 수의 개수
• 어떤 수를 다른 두 수의 합으로 나타낼 수 있는 경우 "좋다" 라고 한다.
• 중복되는 숫자이더라도 위치가 다른 경우 다른 수이다.

풀이

• 좋은 수를 탐색하기 위해 투 포인터를 활용한다.
  • (최대 + 최소 < 원하는 수) 인 경우는 기존 최소를 삭제한다.
  • (최대 + 최소 > 원하는 수) 인 경우는 기존 최대를 삭제한다.
  • 이렇게 L, R을 한 칸씩 움직이며 탐색하고,
  • 조건을 만족하는 경우 바로 return 해준다.
• 알고리즘 내부에서 어떤 수를 활용해 그 수를 만들지 않도록 구현한다.
  • 이때 값이 같아도 위치가 다른 수이면 다른 수이므로 index를 활용한다.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
})

let cnt = 0
const input = () => stdin[cnt++]

let stdin = []
rl.on("line", function (line) {
  stdin.push(line)
}).on("close", function () {
  const N = input()
  const arr = input().split(" ").map(Number)
  arr.sort((a, b) => a - b)
  let count = 0
  for (let i = 0; i < N; i++) {
    if (goodNum(i, 0, N - 1)) count++
  }
  console.log(count)
  process.exit()

  function goodNum(idx, L, R) {
    let sum = 0
    while (L < R) {
      if (L == idx) L++
      if (R == idx) R--
      if (L >= R) return false
      sum = arr[L] + arr[R]
      if (sum == arr[idx]) return true
      if (sum < arr[idx]) {
        L++
      } else {
        R--
      }
    }
    return false
  }
})