[백준] 1522번. 문자열 교환(JAVA)

문제

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

---

풀이(36분)

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = br.readLine();
        int aCount = 0;
        for(int i = 0; i < input.length(); i++){
            if(input.charAt(i) == 'a'){
                aCount++;
            }
        }

        int bCount = Integer.MAX_VALUE;
        for(int i = 0; i < input.length(); i++){
            int idx = i;
            int tempBCount = 0;
            for(int j = 0; j < aCount; j++){
                int nextIdx = (idx + j) % input.length();
                if(input.charAt(nextIdx) == 'b'){
                    tempBCount++;
                }
            }
            bCount = Math.min(bCount, tempBCount);
        }

        System.out.println(bCount);
    }
}

---

문제 풀이 전략

 

실버 1 문제라고 만만하게 봤다가 시간을 매우 오래 쓴 문제이다.

사실 문제를 읽는 순간부터 별다른 아이디어가 떠오르지 않아 고민을 오래 했다.

 

실제로 해결한 아이디어는 꽤나 간단하다.

1. 전체 문장에서 'a'의 개수를 찾는다. -> 궁극적으로 연속해야 할 a의 개수가 된다.

2. 문자열의 각 인덱스마다 a의 개수만큼 잘라서 봤을 때 b가 몇개 있는지 찾는다.

3. 2번 과정에서 최소의 b를 찾는다.

 

무슨 말일까?

aabbaaabaaba 인 문제의 예시를 생각해보자.

1. a의 개수는 8이다.

2.

aabbaaabaaba -> bCount : 3

aabbaaabaaba -> bCount : 3

aabbaaabaaba -> bCount : 3

aabbaaabaaba -> bCount : 3

aabbaaabaaba -> bCount : 2

aabbaaabaaba -> bCount : 2

이런 식으로 모든 인덱스에 대해 'a'의 개수인 8만큼씩 탐색하여 가장 작은 'b'의 개수를 찾는 것이다.

여기서 중요한 것은 원형 배열이기 때문에 % 연산을 통해 뒷 부분까지 모두 탐색해줘야 한다는 것이다.

3. 최종적으로 2에서 bCount : 2가 된다.(뒷 부분은 생략했다.)