[백준 / JAVA] 1522번 문자열 교환

문제

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

먼저 필자는 문제를 이해하는 데에 애를 좀 먹었다. 따라서 문제에 대한 간단한 설명을 추가하겠다.

a를 모두 연속으로 만들기 위해 교환한다는 것은 아래 그림과 같다. 문제에 나온 예시이다.
이렇게 교환이 이루어지는 횟수의 최솟값을 구하면 된다. 위의 예시에서 최솟값은 2이다.

접근

a가 연속적이어야 하기 때문에 입력 문자열에서 어느 부분 문자열이 모두 a가 되어야 한다. 모두 a이기 때문에 부분 문자열의 길이는 a의 총 개수가 된다.

"b로 처리하는 것이 더 나은가?" 생각해보았지만 a가 연속된다는 것은, 곧 b가 연속되는 것과 동일하기 때문에 상관 없다는 결론을 내렸다.

교환 횟수가 최솟값이 되려면 선택한 부분 문자열에서 b의 개수가 최소가 되어야 한다. 즉, a의 총 개수를 길이로 갖는 부분 문자열에서 b의 개수가 최소인 문자열을 찾고, 그 문자열에서 b의 개수가 교환의 최솟값이다.


부분 문자열의 시작 index를 1씩 증가시키면서 b의 개수를 카운트. b의 최솟값과 비교한다.
주의할 것은 문자열이 원형이라는 가정이기 때문에 문자열 범위를 벗어난다면 다시 앞에서 시작하도록 해야 한다.

풀이

코드에서는 접근과 다르게 b가 아닌 a를 카운트한다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine(); // 입력 문자열

        int total = 0; // 입력 받은 문자열에서 a의 개수
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == 'a') total++;
        }

        int aMax = 0; // 부분 문자열에서 a의 개수 중 최댓값
        for (int i = 0; i < str.length(); i++) {
            int aCnt = 0; // 부분 문자열에서 a의 개수 카운트

                for (int j = 0; j < total; j++) {
                // 입력 문자열의 범위를 벗어나면 다시 0부터 시작해야함
                int index = (i + j < str.length() ? i + j : i + j - str.length()); 

                if (str.charAt(index) == 'a') aCnt++;

                if (aCnt > aMax) aMax = aCnt; // 최댓값과 비교
            }
        }

        System.out.println(total - aMax);
    }
}

정리

문제를 이해하는 것이 더 오래 걸린 문제.
원형이라는 가정의 문자열을 어떻게 처리할 것인가 정도만 잘 해결하면 어려울 것은 없었다.