[백준] 1522번 - 문자열 교환 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 문자열에서 최소 교환 횟수로 $a$ 가 연속이 되게 해야한다. 이때 교환은 두 문자의 위치를 바꾸는 것이다. 문자열의 양 끝은 원형으로 연결되어 있다.

예제 입력 1을 예로 들자면, 주어진 문자열은 아래와 같다.

표시된 두 문자를 교환한다.

표시된 두 문자를 교환한다.

표시된 두 문자를 교환한다.

3번의 교환으로 모든 $a$ 가 연속이 된다.

교환 횟수를 구하는 방법은 슬라이딩 윈도우를 활용하면 되는데 문자열 중 $a$ 의 총 개수를 $cnt$ 라고 할 때, $cnt$ 를 크기로 갖는 윈도우를 만들고 이동시키며 윈도우 내에서 가장 $a$ 가 많이 등장한 순간을 찾는 것이다. 윈도우의 크기가 $a$ 의 개수와 같으므로 윈도우 내에 가장 $a$ 가 많이 등장한 순간 윈도우 내 $b$ 와 윈도우 밖 $a$ 를 교환하면 최소 교환 횟수로 모든 $a$ 가 윈도우 내에 연속으로 들어오게 된다. 물론 반대로 $b$ 를 기준으로 해도 된다.

문자열이 원형으로 연결되어 있으므로 모듈러 연산을 통해 인덱스 처리에 신경써줘야 한다.

---

2. 코드

1. 슬라이딩 윈도우 [Java]

import java.io.*;

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

        char[] str = br.readLine().toCharArray();

        int len = 0;  // 윈도우 크기
        for (char c : str) {
            if (c == 'a') len++;
        }

        int cnt = 0;  // 초기 윈도우 내 a의 개수
        for (int i = 0; i < len; i++) {
            if (str[i] == 'a') cnt++;
        }

        int max = cnt;  // 윈도우 내 a의 개수가 가장 많은 경우
        for (int i = 0; i < str.length; i++) {
            if (str[i] == 'a') cnt--;
            if (str[(i + len) % str.length] == 'a') cnt++;

            max = Math.max(max, cnt);
        }

        // 윈도우 내 a의 개수가 가장 많을 때 윈도우 내 b와 윈도우 밖 a를 교환하면 a로 연속되게 교환 가능
        System.out.println(len - max);
    }
}

2. 슬라이딩 윈도우 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    int len = count(s.begin(), s.end(), 'a');          // 윈도우 크기
    int cnt = count(s.begin(), s.begin() + len, 'a');  // 초기 윈도우 내 a의 개수

    int mx = cnt;  // 윈도우 내 a의 개수가 가장 많은 경우
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'a') cnt--;
        if (s[(i + len) % s.size()] == 'a') cnt++;

        mx = max(mx, cnt);
    }

    // 윈도우 내 a의 개수가 가장 많을 때 윈도우 내 b와 윈도우 밖 a를 교환하면 a로 연속되게 교환 가능
    cout << len - mx;
}

---

3. 풀이 정보

1. 슬라이딩 윈도우 [Java]

언어	시간	메모리	코드 길이
Java 11	104 ms	14212 KB	958 B

2. 슬라이딩 윈도우 [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2024 KB	704 B

---