[백준] 고냥이 (JS)

문제

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

고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고양이의 언어로, 고양이의 언어를 사람의 언어로 바꾸어 주는 희대의 발명품이 될 것이다.

현재 고양이말 번역기의 베타버전이 나왔다. 그러나 이 베타버전은 완전 엉망진창이다. 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 굉장히 별로지만 그나마 이게 최선이라고 사람들은 생각했다. 그리고 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지가 궁금해졌다.

고양이와 소통할 수 있도록 우리도 함께 노력해보자.

입력

첫째 줄에는 인식할 수 있는 알파벳의 종류의 최대 개수 N이 입력된다. (1 < N ≤ 26)

둘째 줄에는 문자열이 주어진다. (1 ≤ 문자열의 길이 ≤ 100,000) 단, 문자열에는 알파벳 소문자만이 포함된다.

출력

첫째 줄에 번역기가 인식할 수 있는 문자열의 최대길이를 출력한다. 

시행착오 (시간초과)

처음에는 이중 포문을 이용하여 a부터 뒤에 알파벳을 객체의 key로 할당하면서 key의 개수가 알파벳 종류의 최대 개수를 넘어가면 break로 종료했다. 객체를 초기화 해주고 시작점을 +1씩 바꾸어주면서 각각마다 최대길이를 구해주고 최대값을 리턴했다.
정답을 확인해보니 78%에서 계속 시간초과가 발생했다.
하나의 문자열에서 답을 찾는 과정에서 중첩된 루프가 매번 새로운 구간을 탐색하고, 그 과정에서 문자열을 자르고 다시 처음부터 비교해서 시간복잡도가 O(n^2)이 되었다..

const fs = require("fs");
const input = fs
  .readFileSync("./dev/stdin")
  .toString()
  .trim()
  .split("\n")

Solution = (input) => {
    const alphabetCnt = Number(input[0]);
    const str = input[1];
    const answer = [];
    let compareObj = {};
    
    for (let i = 0; i < str.length; i++) {
        let breakFlag = false;
        for (let j = i; j < str.length; j++) {
            compareObj[str[j]] = compareObj[str[j]] ? compareObj[str[j]] + 1 : 1;
            
            if (Object.keys(compareObj).length > alphabetCnt) {
                breakFlag = true;
                break;
            }
        }
        
        const sum = Object.values(compareObj).reduce((acc, cur) => acc + cur);
        
        answer.push(breakFlag ? sum - 1 : sum);
        compareObj = {};
    }
    
    console.log(Math.max(...answer));
}

Solution(input);

정답

슬라이딩 윈도우를 사용했다. (O(n))
1. left는 윈도우의 시작점, right는 윈도우의 끝점을 나타낸다. 처음에 윈도우 크기를 1로 시작하고, 오른쪽(right)으로 확장하면서 윈도우의 크기를 조절한다.
2. compareObj 객체 생성 후 현재 윈도우 안의 알파벳 수를 카운트한다.
3. compareObj의 키 개수가 alphabetCnt보다 많아지면, left를 오른쪽으로 이동시켜 윈도우 크기를 줄인다.
4. 매번 윈도우 크기를 계산하여 최대 길이를 갱신한다.

const fs = require("fs");
const input = fs
  .readFileSync("./dev/stdin")
  .toString()
  .trim()
  .split("\n")

const Solution = (input) => {
    const alphabetCnt = Number(input[0]);
    const str = input[1];
    let left = 0; // 슬라이딩 윈도우의 시작점
    let answer = 0;
    let compareObj = {};

    for (let right = 0; right < str.length; right++) {
        // 현재 오른쪽 문자를 슬라이딩 윈도우에 추가
        compareObj[str[right]] = compareObj[str[right]] ? compareObj[str[right]] + 1 : 1;
        while (Object.keys(compareObj).length > alphabetCnt) {
            compareObj[str[left]] -= 1;
            if (compareObj[str[left]] === 0) {
                delete compareObj[str[left]];
            }
            left++; // 윈도우의 시작점을 한 칸 오른쪽으로 이동
        }

        // 현재 윈도우 크기 계산 및 최대값 갱신
        answer = Math.max(answer, right - left + 1);
    }
    
    console.log(answer);
}

Solution(input);

결론

골드4의 투포인터 문제이다.
문제를 읽으면서 객체의 key 개수로 쉽게 풀 수 있겠다 생각하였는데 시간 초과에 걸려 애를 먹었다..
슬라이딩 윈도우 기법에 대하여 공부할 수 있었다.