[boj] 13144. List of Unique Numbers (node.js)

요약

13144

• 입력: 길이가 N인 수열
• 주어진 수열에서 1개 이상의 연속하는 숫자들을 뽑는 상황
• 출력: 같은 수가 여러 번 등장하지 않는 경우의 수

풀이

연속적인 숫자들을 뽑는 상황이므로 투 포인터를 활용한다.

내 풀이

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);
  let result = 0;
  const count = new Array(100000 + 1).fill(0);
  for (let L = 0, R = 0; L < N; L++) {
    while (R < N && count[arr[R]] == 0) {
      count[arr[R++]]++;
    }
    count[arr[L]] = 0;
    result += R - L;
  }
  console.log(result);
  process.exit();
});

• 효율적인 탐색을 위해 두 포인터 L, R, 그리고 이미 포함된 값인지 확인하기 위해 count 배열을 활용한다.
• 연속과 중복 원소가 없는 최대 범위까지 R을 확장시킨 후에, 더 이상 확장시킬 수 없는 경우 범위 내에 존재하는 1개 이상 연속되는 숫자들의 개수를 더한다. 이는 R - L 이라는 거리 계산식으로 간단하게 셀 수 있다.