[백준] 1522 문자열 교환 풀이 java

1. 문제 설명

문제 설명

2. 접근 방식

KEY WORD: Sliding Window, 나머지 연산

아이디어를 떠올리기가 어려워서 다른 사람의 풀이 블로그에서 아이디어 부분까지만 봤다.
나는 a와 b를 일일히 교환하는데만 집중하고 있었는데, 완전히 잘못된 접근 방식이었다. 그러한 방식으로 풀었을 때, 최소값을 어떻게 찾을 수 있을지 감이 안온다.

문제를 푸는 방식은 다음과 같다.

1. 문자열 내의 a의 개수를 세고, 그 개수를 용량으로 하는 Sliding window를 만든다.
2. 문자열의 처음부터, 1번에서 센 슬라이딩 윈도우의 용량만큼 a와 b의 개수를 센다.
3. b의 개수 == 교환이 일어나는 횟수 이다. 현재 a의 개수만큼씩 배열을 확인하고 있고, 거기서 b의 개수를 전부 a로 돌린다면, 연속된 a와 연속된 b가 만들어진다. 따라서 b를 교환하는 횟수가 가장 적은 경우를 찾아서 그것의 숫자를 세면, 답이 된다.

3. 코드 분석

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int cntA = 0;
        int [] cnts = new int [2]; // 0 -> a, b -> 1
        // a가 몇개인지 카운트
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == 'a') cntA++;
        }
        // 슬라이딩 윈도우 초기화
        for (int i = 0; i < cntA; i++) {
            if(s.charAt(i) == 'a') cnts[0]++;
            else if (s.charAt(i) == 'b') cnts[1]++;
        }

        if(cnts[0] == cntA) {
            System.out.println(0);
            return;
        }

        int min_change = Integer.MAX_VALUE;

        for (int i = cntA; i < s.length()*2; i++) {
            int start = (i - cntA)%(s.length());
            int end = i%(s.length());
            // 슬라이딩 윈도우를 이동하며, a와 b의 개수 갱신
            if(s.charAt(start)  == 'a') cnts[0]--;
            else cnts[1]--;
            if(s.charAt(end)    == 'a') cnts[0]++;
            else cnts[1]++;
            // 최소값 갱신
            min_change = Math.min(min_change, cnts[1]);
        }
        System.out.println(min_change);
    }
}

4. 성장하기

해당 문자열은 시작과 끝이 맞붙어 있는 원형의 형태이다. 따라서 배열의 끝부분 => 시작부분 까지의 슬라이딩 윈도우도 계산해야 한다. 따라서 두 가지를 신경 써야 한다.

1. Loop의 길이 -> 단순하게 문자열을 선형적으로 신경써서는 안된다. 슬라이딩 윈도우 기준 한 바퀴가 되도록 Loop의 총량을 정해야 한다. 여기서는 Sliding window의 길이 + 배열의 길이 가 될 것이다. (위의 코드에서는 이런 것들 안 따지고 배열의 길이*2를 하여 문제를 풀었다.)
2. 1번처럼 Loop의 길이를 정하면, 원래 문자열 길이가 15였을 시, for문의 i가 가리키는 값이 16,17... 이 될 지 모른다. 이렇게 되면, s.charAt(i)가 문자열의 길이를 벗어난다! 우리는 여기서 어떻게 해결해야 하는가?
   i%(문자열의 길이)를 하면 된다. 위에서 예시로 들었듯이, 문자열의 길이가 15라고 해보자. 그러면 15%15 == 0임으로, 16,17 ... 로 나아갈수록 문자열의 처음부터 다시 시작할 수 있다.