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

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

 

문제 요약

원형으로 이어진 문자열에서 'a'들을 하나의 연속된 구간으로 만들기 위해 필요한 최소 교환 횟수를 구한다.
교환은 문자 위치를 바꾸는 것으로 생각할 수 있으며, 최소 횟수를 구해야 한다.

'a'를 연속으로 만드는것과 교환을 하는 과정이 문제에는 상세하게 적혀있지 않아서 이 부분에서 조금 시간이 걸렸다. 

---

핵심 아이디어

1) “만들어야 하는 구간 길이”는 고정이다

문자열 전체에서 'a'의 개수를 K라고 하자.
최종적으로 'a'가 연속된 구간이 되려면 길이가 반드시 K인 구간 안이 전부 'a'여야 한다.

즉, 길이 K인 어떤 구간을 잡았을 때
그 구간 안에 'b'가 몇 개 들어있는지가 중요하다.

• 구간 안 'b'가 x개면 → 밖의 'a'와 x번 교환하면 구간을 전부 'a'로 만들 수 있다.
• 따라서 답은 “길이 K 구간들 중 'b' 개수의 최소값”이다.

---

원형 처리

문자열은 원형이므로 끝을 넘어가는 구간도 고려해야 한다.
이를 간단히 처리하려고 문자열을 두 번 이어붙인다.

S = S + S

그러면 원래 문자열에서 시작점 0 ~ N-1만 확인해도
원형 구간을 모두 선형 구간처럼 확인할 수 있다.

---

슬라이딩 윈도우

길이 K인 창을 한 칸씩 오른쪽으로 이동시키면서 'b' 개수를 업데이트한다.

• 처음 창(0~K-1)의 'b' 개수 계산
• 다음 창으로 이동할 때:
  • 왼쪽에서 빠지는 문자 1개 반영
  • 오른쪽에서 들어오는 문자 1개 반영

이렇게 하면 매 창을 O(1)에 갱신 가능 → 전체 O(N)

 

처음에는 이중 포문을 돌며 최악의 경우 O(N)의 풀이를 사용했지만 피드백 이후 이런식으로 고쳐서 O(N)만에 문제를 풀 수 있게 만들었다.

 

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

public class Main {
    public static int N;
    public static String str;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        N = str.length();

        // 1. a의 총 계수 계산 -> 윈도우 크기
        int k = 0;
        for(int i = 0; i < N; i++){
            if(str.charAt(i) == 'a') k++;
        }

        // ** 엣지 케이스 ** a 가 0 이거나 n이면 교환 불필요
        if(k == 0 || k == N){
            System.out.println(0);
            return;
        }

        // 2. 원형처리 => 초기 문자열 이어 붙이기
        String t = str + str;

        // 3. 초기 창의 b 갯수
        int bCnt = 0;
        for(int i = 0; i < k; i++) {
            if(t.charAt(i) == 'b') bCnt++;
        }

        int ans = bCnt;

        // 4. 슬라이딩 윈도우 : 시작점 1 ~ N - 1 까지만 보면 충분
        for(int i = 1; i < N; i++){
            if(t.charAt(i - 1) == 'b') bCnt--;
            if(t.charAt(i + k - 1) == 'b') bCnt++;
            ans = Math.min(ans, bCnt);
        }

        System.out.println(ans);
    }
}

 

 

복잡도 분석

• 'a' 개수 세기: O(N)
• 초기 창 계산: O(K) (K ≤ N)
• 슬라이딩: O(N)

총 시간복잡도: O(N)
공간복잡도: 문자열 2배 사용하므로 O(N)

---

정리 / 느낀 점

이 문제는 “교환”이라는 말 때문에 복잡해 보이지만, 실제로는
길이가 고정된 구간에서 'b'를 최소로 찾는 문제로 변환하는 게 핵심이다.
원형 문자열은 S+S로 펴서 슬라이딩 윈도우를 적용하면 깔끔하게 해결된다.