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

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

1522번: 문자열 교환

 

문제 분석

a와 b로만 이루어진 문자열이 있다. 이 문자열에서 a가 모두 연속이 되게 하기 위해 a와 b의 위치를 교환할 것인데, 이 때 교환 횟수의 최솟값을 구하는 것이 문제이다. 이 문자열은 원형이라서, aabbbba 역시 a가 모두 연속되어있다고 할 수 있다.

 

처음에는 사실 문제를 이해하지도 못했다. 문제에선 그저 교환이라고만 되어있어서, 나는 이게 b라는 문자를 a로 바꿀 수 있다 라는 의미의 교환인지, 아니면 문자열 내 i번째 문자와 j번째 문자의 위치를 서로 바꿀 수 있다 라는 의미의 교환인지 이해하는 데 오래 걸렸다. 문제에서 말하는 '교환' 이란, 후자 (문자열 내 i번째 문자와 j번째 문자의 위치를 서로 바꿀 수 있다) 를 의미한다.

 

교환의 의미를 명확히 했으니, 문제를 어떻게 풀어야 할 지에 대해 다시 생각을 해보도록 하자. 문자열을 a는 a끼리, b는 b끼리 몰아주면서 교환의 횟수는 최소한으로 한다는 게 어떤 의미일까 ?

 

문자열이 주어지면, 우리는 이 문자열을 특정 크기의 윈도우(window)만큼만 볼 것이다. 나는 이 때 윈도우의 크기를 편의상 문자열에서 a가 나오는 횟수로 지정했다. 문제의 예시와 함께 살펴보도록 하자.

 

'aabbaaabaaba'

 

위 문자열에서, a는 8개, b는 4개이다. 그래서 나는 윈도우의 크기를 8로 잡고, 이 문자열의 일부만 보기 시작할 것이다. 가장 먼저 index [0, 8) 구간을 살펴보도록 하겠다.

 

[0, 8) - 'aabbaaab'

 

문제에서 말하는 교환의 최종 결과인 'a가 모두 연속이 되게' 하려면, 크기가 8(a의 총 수)인 윈도우 안에 a를 다 넣어야 한다. 이게 의미하는 바는, 윈도우 안의 b들을 윈도우 밖의 a들과 교환해야 한다는 것이다. 즉, 윈도우를 맨 앞부터 맨 뒤까지 (정확히 말하면 원형 문자열이기 때문에 [0, 8) 부터 [11, 7)까지 봐야 함) 이동시켜가면서, 윈도우 안에 b의 개수가 최소일 때를 찾으면 그것이 바로 교환 횟수의 최솟값이 되는 것이다.

 

코드

#include <iostream>
#include <cstring>

using namespace std;

string input;
int result;

void getInput() {
    cin >> input;
}

void solve() {
    result = input.length();

    int aCount = 0;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == 'a') {
            aCount++;
        }
    }

    int bCount = 0;
    for (int i = 0; i < aCount; i++) {
        if (input[i] == 'b') {
            bCount++;
        }
    }
    result = min(result, bCount);

    for (int i = 0; i < input.length(); i++) {
        if (input[i] == 'b') {
            bCount--;
        }

        if (input[(i + aCount) % input.length()] == 'b') {
            bCount++;
        }

        result = min(result, bCount);
    }
}

void printResult() {
    cout << result << "\n";
}

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

    getInput();
    solve();
    printResult();

    return 0;
}

 

코드 설명

코드 자체는 어려운 부분이 크게 없으나, 유의해야 할 점은 원형 문자열이기 때문에 윈도우를 [0, 8) 부터 [4, 12)까지만 이동시키는 것이 아니라, [0, 8)부터 [4, 12)를 거쳐 [11, 7)까지 이동시켜가며 확인해야 한다는 점이다. 그래서 나는 윈도우를 이동시키는 부분의 코드를 이렇게 작성했다.

 

    for (int i = 0; i < input.length(); i++) {
        if (input[i] == 'b') {
            bCount--;
        }

        if (input[(i + aCount) % input.length()] == 'b') {
            bCount++;
        }

        result = min(result, bCount);
    }

 

i는 윈도우에서 벗어나게 되는 인덱스를 의미하고, (i + aCount)는 윈도우에 새로이 포함되게 되는 인덱스를 의미한다. 그런데 이 (i + aCount)가 입력 문자열의 길이를 넘을 수 있으므로 % input.length()로 처리해주었다.