[JavaScript] 백준 골드 4 : 13144 - List of Unique Numbers

https://www.acmicpc.net/problem/13144

---

풀이

경우의 수를 묻는 일이라서 dp를 생각했었다. 가장 긴 부분 수열 찾기 그런 느낌으로 풀어야 할줄 알고 dp로 짜보려고 했는데 마지막 값을 기준으로 확인하는게 아니라 현재 부분에서의 모든 숫자 사용 여부를 알아야 해서 그렇게 하긴 좀 어렵겠다 싶다가 투포인터로 풀게 되었다.

• start는 순차적으로 증가시킨다.
• end는 매 start 단계마다 중복된(현재 수열에 이미 존재하는) 숫자가 다시 나올 때까지 증가시킨다.
  • 새로 나온 숫자들은 방문 배열에 넣어준다.
• 현재 start를 시작점으로 하는 중복 숫자 없는 수열은 end - start 개이기 때문에 이 숫자를 정답에 더해준다.
  • end가 정확하게 중복없는데서 끝난다면 end - start + 1이겠지만, end가 ++로 인해 한단계 더 뒤로 가있기 때문에 end - start로 개수를 세준다.

정답 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\\n");

const n = +input[0];
const list = input[1].split(" ").map(Number);

let start = 0;
let end = 0;

const used = new Set();
let count = 0;

for (start; start < list.length; start++) {
  while (end < list.length && !used.has(list[end])) {
    used.add(list[end]);
    end++;
  }
  count += end - start;
  used.delete(list[start]);
}

console.log(count);