[백준] 문자열 교환 (JS)

문제

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

a와 b로만 이루어진 문자열이 주어질 때,  a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오.

이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다.

예를 들어,  aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 1,000이다.

출력

첫째 줄에 필요한 교환의 회수의 최솟값을 출력한다.

풀이

1. 먼저, 문자열 내에 있는 'a'의 개수를 센다. 이는 연속으로 만들고자 하는 'a'의 총 개수이다.

2. 문자열이 원형이므로, 처음과 끝이 이어질 수 있도록 문자열을 뒤에 이어 붙인다.

3. 이어 붙인 문자열에서 'a'의 개수만큼 슬라이딩 윈도우를 설정하고, 각 구간마다 'b'의 개수를 센다.

4. 그중 'b'의 개수가 가장 적은 윈도우가 존재하는 위치가, 'a'를 연속시키기 위해 최소한의 교환만 필요한 구간이다. 이때의 'b' 개수가 곧 최소 교환 횟수다.

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

Solution = (input) => {
    const aCnt = input.filter(str => str === "a").length;
    const doubled = input.concat(input);

    let min = Infinity;
    
    for (let i = 0; i < input.length; i++) {
         const sliceStr = doubled.slice(i, i + aCnt);
         const bCnt = sliceStr.filter(str => str === "b").length;
         if (bCnt < min) min = bCnt;
    }
    
    console.log(min);
}

Solution(input);