[백준] 20437 문자열 게임 2 (Javascript)

문제

BOJ20437_문자열 게임

요구사항

알파벳 소문자로 이루어진 문자열 W가 있고, 양의 정수 K가 주어졌을 때 아래 두 조건에 각각 만족하는 문자열의 길이를 구하시오.

• 어떤 문자를 정확히 K개 포함하는 가장 짧은 연속 문자열
• 어떤 문자를 정확히 K개 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs')
    .readFileSync(filePath)
    .toString()
    .trim()
    .split('\n')
    .map((e) => e.trim());

let T = +input[0];
let idx = 1;
let answer = '';

while (T--) {
    const W = input[idx++];
    const K = +input[idx++];

    let answerThree = Infinity;
    let answerFour = 0;

    const obj = {};

    for (let i = 0; i < W.length; i++) {
        const char = W[i];
        // 문자의 인덱스 저장
        if (!obj[char]) obj[char] = [i];
        else obj[char].push(i);
    }

    for (const char in obj) {
        // 어떤 문자를 K개 포함할경우 가장 짧은 연속 문자열 찾기
        if (obj[char].length >= K) {
            const arr = obj[char];

            for (let i = 0; i <= arr.length - K; i++) {
                const [left, right] = [arr[i], arr[i + K - 1]];
                answerThree = Math.min(answerThree, right - left + 1); // 최소 길이
                answerFour = Math.max(answerFour, right - left + 1); // 최대 길이
            }
        }
    }
    if (answerThree === Infinity || answerFour === 0) {
        answer += -1 + '\n';
    } else {
        answer += answerThree + ' ' + answerFour + '\n';
    }
}

console.log(answer.trimEnd());

접근법

• 객체 리터럴의 키를 알파벳 소문자로 하고, 값으로는 배열을 갖도록 한다. 이 배열은 키 값과 일치하는 문자의 인덱스를 배열에 저장해둔다.
  
• 키 값을 순회하며 키 값에 대응하는 배열의 길이가 $K$보다 크거나 같은지 확인한다. 만약 배열의 길이가 $K$보다 작을 경우에는 해당 문자를 $K$개 포함하지 못하기 때문이다.
• 배열의 길이가 $K$보다 크거나 같다면 '슬라이드 윈도우'를 진행해준다. 하나의 배열에는 전부 같은 문자의 인덱스만 들어있고, 해당 문자를 정확히 $K$개 포함해야 하므로 슬라이드 윈도우의 폭은 $K$로 지정해준다.
• $큰 \ 인덱스 - 작은 \ 인덱스 + 1$을 어떤 문자를 정확히 K개 포함하는 문자열의 길이를 구할 수 있고, 현재까지 누적해온 최소 길이, 최대 길이와 비교해서 값을 갱신해준다.
• 모든 문자를 순회했을 때 '3번 조건' 에 만족하는 문자열이 없거나, '4번 조건' 에 만족하는 문자열이 없다면 -1을 정답에 저장하고, 아니라면 정답을 누적한다.