문제

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

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

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

입력

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

출력

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

예제 입력

abababababababa

예제 출력

3

내가 했던 풀이 방법

a를 모두 연속으로 만들기 위함일 뿐 a와 b로 분리를 할 필요는 없다. 문자열이 원형이기 때문에 aaabbaaa도 가능하다. 결국 a를 모두 연속으로만 만들면 되므로 a개의 개수만큼의 문자열 안에 b가 최소가 되는 경우를 계산해주면 된다. a개 개수 길이 안에 b가 3개 존재하는 경우와 2개 존재하는 경우를 생각해보면 각 b를 3번, 2번 a와 교환해주면 모든 문자열이 a가 될 것이기 때문이다. 즉, 슬라이딩 윈도우에서 윈도우의 크기를 a의 개수로 하고 윈도우 안에 b가 최소인 경우를 찾아주면 된다.

1. 문자열을 배열로 변경해준다.
2. aCount에 문자열 내에 a 개수를 저장해준다.
3. 문자열 배열을 하나 더 합친 circular 배열을 만들어준다. aaabbaaa의 경우 aaabbaaaaaabbaaa가 된다. 원형이기 때문에 무한하다고 생각해주면 되는데 한 번만 합쳐줘도 윈도우 크기는 문자열 전체 길이보다 커질 수가 없어서 모든 경우를 다 확인해줄 수 있다.
4. 0부터 aCount 길이만큼의 문자열에서의 b의 개수를 계산하고 currentBCount와 min에 저장해준다.
5. 1부터 순차적으로 반복하며 이전 문자열이 b일 경우 currentBCount를 1 감소시켜주고, 새로 윈도우에 들어온 문자열이 b일 경우 1을 증가시켜준다. 매 연산마다 currentBCount와 min의 최솟값을 계산한다.
6. 모든 연산이 끝난 뒤 min 값을 출력한다.

코드

var fs = require('fs');
let str = fs.readFileSync(0, 'utf-8').toString().trim();

str = str.split('');
let aCount = 0;
for (let i = 0; i < str.length; i++) {
  if (str[i] === 'a') {
    aCount++;
  }
}

let circular = str.concat(str);
let currentBCount = 0;
for (let i = 0; i < aCount; i++) {
  if (str[i] === 'b') {
    currentBCount++;
  }
}

let min = currentBCount;

for (let i = 1; i < str.length; i++) {
  if (circular[i - 1] === 'b') {
    currentBCount--;
  }
  if (circular[i + aCount - 1] === 'b') {
    currentBCount++;
  }
  min = Math.min(currentBCount, min);
}

console.log(min);

회고

문제 풀이보다는 문제 이해하는 데 굉장히 오래걸렸던 문제 실버1이 되고나서 문제를 이해 못하는 경우가 너무 늘어났는데, 티어 상승하면서 국어 비문학을 푸는 느낌이 든다...