문자열 교환 (백준 1522번)

문제

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

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

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

입력

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

출력

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

예제 입력 1

abababababababa

예제 출력 1

3

예제 입력 2

ba

예제 출력 2

0

예제 입력 3

aaaabbbbba

예제 출력 3

0

예제 입력 4

abab

예제 출력 4

1

예제 입력 5

aabbaaabaaba

예제 출력 5

2

예제 입력 6

aaaa

예제 출력 6

0

---

🚀문제 접근

문자열이 원형이다 이런 정보때문에 원형큐 문제인지 접근하는 과정이 매우 헷갈렸다.

먼저 ababa 라는 문자열이 있다고 생각해보자.

이 문자열에서 a를 모두 연속하게 만들려면 최소 a의 갯수만큼의 영역을 확보해야한다.

위 문자열에서는 a가 세 개 있으므로 aaa 라는 size가 3인 영역을 확보해야한다는 뜻이다.

그림과 같이 3개의 영역을 확보하고 옆으로 쭉 밀면서 교환횟수를 구한다음 최솟값을 리턴하면 된다. 즉, 슬라이딩 윈도우이다.

교환횟수는 영역 안에 있는 b의 갯수이다.

🛠코드

let input = require('fs').readFileSync(0).toString().trim();

function solution() {
  let ret = Number.MAX_SAFE_INTEGER;
  let window = 0;
  for (let i = 0; i < input.length; i++) {
    if (input[i] === 'a') window++;
  }
  for (let i = 0; i < input.length; i++) {
    let windowSize = window;
    let j = i;
    let cnt = 0;
    while (windowSize) {
      if (j >= input.length) j -= input.length;
      if (input[j] === 'b') cnt++;
      j++;
      windowSize--;
    }
    if (ret > cnt) ret = cnt;
  }

  return ret;
}

console.log(solution());

 

아래 코드가 더 깔끔하게 정리가 잘 된 거 같다.

let input = require('fs').readFileSync(0).toString().trim();

function solution() {
  let ret = Number.MAX_SAFE_INTEGER;
  let windowSize = 0;

  for (let i = 0; i < input.length; i++) {
    if (input.charAt(i) === 'a') windowSize++;
  }

  for (let i = 0; i < input.length; i++) {
    let bCount = 0;
    for (let j = i; j < i + windowSize; j++) {
      let idx = j % input.length;
      if (input.charAt(idx) === 'b') bCount++;
    }
    ret = Math.min(ret, bCount);
  }

  return ret;
}

console.log(solution());