[JavaScript/node.js] 백준 1522번 - 문자열 교환

[문제]

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

1522번: 문자열 교환

 

[풀이]

1. a를 모두 연속적으로 만들기 위해선 우선 문자열의 총 a 개수를 구해야 합니다.
2. a의 총 문자 개수(len)의 구간으로 슬라이딩 윈도우를 통해 구간에 포함된 a의 개수를 구합니다.
3. (총 a의 개수(len)) - (가장 많은 개수를 포함한 구간의 a개 수)를 통해 최소 이동 횟수를 구합니다. 

 

예를 들어 문자열이 "ababa"라고 한다면 풀이 과정은 다음과 같습니다.

 

len = 3 이므로 3 구간씩 이동하며 길이를 구하는데, 이때 슬라이딩 윈도우를 사용합니다.

 

• 초기값으로 인덱스 aba 에서 a의 개수를 구하면 sum = 2입니다.
• 다음 구간부턴 새로 들어온 값이 b 이고, 구간에서 제외된 값이 a 이므로 sum + 0 - 1 = 1로 bab는 1이 됩니다. 
• 위 과정을 반복하여 마지막 구간까지 구하면 최대 sum 값은 2가 되므로 b를 1번만 교체하면 연속된 aaa를 만들 수 있습니다. 따라서 최소 교체 횟수는 1입니다.

[코드]

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

const word = input[0].split("").map(String);

const len = word.filter((i) => i === 'a').length;

// len 씩 슬라이딩 윈도우를 해서 a가 가장 많은 구간 찾기

// 초기값 세팅
let sum = 0;
for(let i=0;i<len;i++) {
    sum += word[i] === 'a' ? 1 : 0;
}

// 가장 큰 값 찾기 위해 세팅
let max = sum;

for(let i=len;i<word.length + len - 1;i++) {
    let w;

    // 새로운 값 더하기
    if(i >= word.length) {
        w = word[i-word.length];
    } else {
        w = word[i];
    }
    sum += w === 'a' ? 1 : 0;

    // 이전값 빼기
    sum -= word[i-len] === 'a' ? 1 : 0;

    if(sum > max) {
        max = sum;
    }
}

// (전체 a의 수 - 최대 연속수 = 최소 이동 횟수)

console.log(len - max);