백준 1522번 문자열 교환 (C++)

문제 링크 : https://www.acmicpc.net/problem/1522

1522번: 문자열 교환

문제 요약

 

1. 문자열 s는 원형이기 때문에 처음과 끝은 서로 붙어있습니다.

2. 문자열 s에서 a를 모두 연속으로 만들기 위한 문자의 최소 교환 횟수를 출력하세요.

 

 

핵심 포인트

 

1. 문자는 1대1로 교환이 가능합니다. 즉, 'a'<->'b'처럼 각각 1개씩 교환이 가능하며, 교환된 문자는 서로 자리가 바뀌게 됩니다.

2. 문자열의 최대 길이는 1,000입니다. 2중 for문을 돌려도 시간초과가 나지 않을 길이입니다.

때문에 알고리즘 분류에는 브루트포스도 포함되어 있습니다.

 

 

문제 풀이

 

1. 변수를 선언하고 값을 입력받습니다. 이때 문자열 s에서 a개의 갯수는 따로 저장해줍니다.

    string s;
    cin >> s;
    int a=0, ans=s.size(); // a=0으로 초기화 하는것을 잊지마세요!
    for(auto c : s) if(c=='a') a++;

 

2. 2중 for문을 돌립니다.

for(int i=0; i<s.size(); i++){
        int cnt = a, temp = 0; // 1
        for(int j=i; j<i+s.size(); j++){ // 2
            if(cnt==0) break; // 3
            if(s[j%s.size()]=='b') temp++, cnt--; // 4
            else cnt--; // 5
        }
        ans = min(ans,temp); // 6
    }

(1) cnt는 한 곳으로 몰아 넣어야하는 a의 갯수이며 temp는 자리를 바꿔야할 'b'의 갯수입니다.

(2) i부터 i+s.size()까지 for문을 돌립니다. 슬라이딩 윈도우 기법을 활용하여, 원형으로 이어진 문자열 전체를 탐색하기 위함입니다.

(3) 만약 cnt=0이라면 for문을 종료합니다. 모든 a를 1개의 그룹으로(=연속으로) 묶어주었기 때문이 더 진행할 필요가 없습니다.

(4) 만약 현 위치의 문자가 'b'라면 temp는 +1, cnt는 -1을 합니다. cnt를 -1하는 이유는 b와 자리를 바꿨기 때문에 전체에서 한 곳으로 몰아 넣어야하는 'a'의 갯수가 하나 줄었기 때문입니다.

추가로 문자열의 마지막 사이즈에 도달했을 경우 다시 0번째로 되돌아가기 위해 j%s.size()의 위치를 파악하는 것을 잊지마세요.

(5) 반대로 현 위치의 문자가 'a'라면 cnt를 -1합니다.

(6) ans는 ans와 temp중 최소값을 저장합니다.

 

3. 정답을 출력합니다.

 

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string s;
    cin >> s;
    int a=0, ans=s.size();
    for(auto c : s) if(c=='a') a++;
    for(int i=0; i<s.size(); i++){
        int cnt = a, temp = 0;
        for(int j=i; j<i+s.size(); j++){
            if(cnt==0) break;
            if(s[j%s.size()]=='b') temp++, cnt--;
            else cnt--;
        }
        ans = min(ans,temp);
    }
    cout << ans << "\n";
    return 0;
}