[백준] 16472 고냥이 - javascript

📌 문제

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

📌 풀이

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

let N = +input.shift();
let str = input.shift();

let left = (right = ans = 0);
const alphabet = new Map();

while (left <= right && right < str.length) {
  const curAlphabet = str[right];

  alphabet.set(curAlphabet, (alphabet.get(curAlphabet) || 0) + 1);

  while (alphabet.size > N) {
    if (alphabet.get(str[left]) === 1) {
      alphabet.delete(str[left]);
    } else {
      alphabet.set(str[left], alphabet.get(str[left]) - 1);
    }
    left++;
  }

  ans = Math.max(ans, right - left + 1);
  right++;
}
console.log(ans);

✔ 알고리즘 : 투포인터

✔ left, right 포인터를 0으로 초기화 시키고 str을 순회한다.

✔ 알파벳의 종류와 해당 알파벳의 개수를 저장하기 위해 map 자료구조를 사용하였다.

✔ right가 이동할때마다 map자료구조에 추가를 해주고 alphabet.size로 현재 map자료구조에 알파벳이 몇종류가 있는지 확인한다.

✔ N보다 종류가 많을 시 N이 될때까지 left 포인터를 이용하여 map 자료구조에서 제거해준다. 이 때 알파벳의 개수가 1인 경우는 map 자료구조에서 delete 시켜준다.

✔ 난이도 : 백준 기준 골드 4