[백준] 1522 문자열 교환 (Javascript)

문제

BOJ1522_문자열 교환

풀이

문제 정의

'a'와 'b'로 구성된 문자열이 있다. 이때 a를 모두 연속되게 배열하려면 최소 몇 번의 교환이 이루어져야 하는지 구하시오
문자열의 시작과 끝은 원형으로 연결되어있다.

해결방안

이 문제는 슬라이딩 윈도우로 풀 수 있다.

문자열 abababa가 주어졌다고 가정해보자.
'a'를 연속되게 만들어야 하므로 'a'의 개수를 구하고, 이를 슬라이딩 윈도우의 범위로 정하는 것이다.
그리고 이 범위를 괄호로 묶어보면 아래와 같다.
(abab)aba

이렇게 괄호가 만들어졌을 때, 괄호 안에는 'a'만 남기고, 괄호 밖에는 'b'만 남도록 교환을 수행해주자.
(aaab)bba
(aaaa)bbb
총 2회만에 모든 a를 연속으로 만들었다.
즉 괄호 안의 b의 개수가 교환 횟수가 되는 것이다.
현재 최솟값을 2로 갱신해주고 탐색을 이어나간다.

a(baba)ba
b(aaba)ba
b(aaaa)bb

이번에도 2회다. 이런식으로 전부 탐색해주면 된다.

또한 문자열은 시작과 끝이 연결되어있는 원형 형태이기 때문에 아래와 같은 경우도 고려해줘야 한다.

a)bab(aba
ab)aba(ba
aba)bab(a

이것은 "a의 개수-1"개 만큼의 앞쪽 문자열을 뒤에 그대로 이어줌으로써 해결할 수 있다.

a)bab(aba = abab(abaa)ba
ab)aba(ba = ababa(baab)a
aba)bab(a = ababab(aaba)

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
let input = require('fs').readFileSync(filePath).toString().trim();
const N = input.length;
const countA = input.match(/a/g)?.length;
input += input.slice(0, countA - 1);
let min = Infinity;

for (let i = 0; i < N; i++) {
    const substring = input.slice(i, i + countA);
    min = Math.min(min, substring.match(/b/g)?.length || 0);
}
console.log(min);