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

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

풀이

직접 교환을 진행하는 것보단 최소 횟수로 교환이 진행된 문자열과 비교를 통해 총 몇 번 교환해야 하는지를 알아내는 방식이 나을 것 같았다(풀고 나서 알았지만 이와 같은 방식을 슬라이딩 윈도우 알고리즘이라고 한다)

 

입력받은 문자열에서 a만 남긴 문자열을 만들어주고, 해당 문자열을 오른쪽으로 한 칸씩 이동시켜가며 입력받은 문자열과 일대일로 비교하며 다를 경우 count를 올려준다

 

문자열의 끝은 서로 연결되어 있다고 가정하기 때문에 만약 문자열의 길이를 넘어간 인덱스에 접근할 차례면 앞으로 보내준다

이런 식으로 한 칸씩 이동해 가면서 요소들을 비교하는 식으로 진행하였다

오른쪽으로 계속 이동하다 문자열의 길이를 넘어가는 경우 위와 같이 비교한다

 

최종적으로 가장 적은 횟수를 출력한다

 

제출 코드

#include <iostream>
using namespace std;

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

    string str, comp = "";
    cin >> str;

    for(auto c : str)
        if (c == 'a')  comp += "a";

    int minEx = 1000;
    int len = str.length();
    for (int i = 0; i < len; i++)
    {
        int count = 0;
        for (int j = 0; j < comp.length(); j++)
        {
            int idx = (i + j >= len) ? i + j - len : i + j;
            if (str[idx] != 'a') count++;
        }
        minEx = min(minEx, count);
    }
    cout << minEx;
}