백준 1522 - 문자열 교환

문제 설명

a와 b로만 이루어진 문자열이 주어질 때,  a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오.

이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다.

예를 들어,  aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, a와 b로만 이루어진 문자열이 주어지면 적절히 문자를 바꿔 a가 연속하도록 바꿔야 한다.

a가 연속하도록 변경하려면 최소 몇 번 바꿔야 하는지 계산해야 한다.

 

해당 문제는 접근법만 정립하면 간단하게 풀리는 문제이다.

a가 연속하다는 얘기는 b도 연속하다는 얘기가 된다.

b사이에 a가 존재하면 조건에 충족되지 않기 때문이다.

 

따라서, b의 개수를 구한 뒤, 특정 인덱스부터 b가 연속으로 존재한다고 가정하면, 몇 개의 a를 바꿔야 하는지 세면 된다.

예를 들어, 

b의 개수는 4개이기 때문에 0번 인덱스부터 bbbb를 만들려면 a를 2개 바꿔야 한다.

1번 인덱스부터도 마찬가지로 2개를 바꾸면 된다.

즉, 초록색 범위의 a의 개수가 바꿔야할 개수와 일치한다.

따라서, i번 인덱스부터 cnt(b의 개수)만큼 배열을 순회하며 a의 개수를 세면 된다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

string str;
int cnt;

int Count(int idx)
{
	int ret = 0;
	int len = str.length();
	for (int i = idx; i < idx + cnt; i++)
	{
		if (str[i % len] == 'a') ret++;
	}

	return ret;
}

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

    cin >> str;
	
	cnt = 0;
	int ans = INT_MAX;
	for (int i = 0; i < str.length(); i++)
	{
		if (str[i] == 'b') cnt++;
	}

	for (int i = 0; i < str.length(); i++)
	{
		ans = min(ans, Count(i));
	}

	cout << ans;

    return 0;
}

 

---