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

문제

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

1522번: 문자열 교환

 

문제이해

• 첫째 줄에 문자열을 입력한다.
• 교환 횟수의 최솟값을 출력한다.

문자열은 원형으로 되어있으며 문자열은 a와 b로만 이루어져 있다. a를 모두 연속으로 만든다는 것은 a를 모두 모은다는 것이고 이 말은 b를 모두 모은다는 말과 똑같은 말이다. b를 모두 모으는데 필요한 교환의 최솟값을 구하기 위해서는 b를 최소한으로 교환하는 경우를 찾아야 한다. 문자열을 최소한으로 교환하기 위해서는 이미 b들이 제일 많이 모여있는 부분에 b를 모아주면 된다. 문자열 내에서 b의 개수를 구한 다음 원형의 문자열에서 b의 개수만큼의 길이를 가진 연속된 문자열들 중에서 b가 가장 많이 모여있는 문자열을 찾으면 된다. 이후 그 문자열에 a가 몇 개 있는지만 구해서 출력해주기만 하면 된다.

 

문제풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

void result(string str) {
	int bCount{ 0 };
	for (char c : str)
		if (c == 'b')
			bCount++;
	int start = 0;
	int end = bCount - 1;
	int startTemp{}, endTemp{}, bTemp{};
	while (start != str.length()) {
		if (start <= end) {
			int count{};
			for (int idx{ start }; idx <= end; idx++) {
				if (str[idx] == 'b')
					count++;
			}
			if (count > bTemp) {
				bTemp = count;
				startTemp = start;
				endTemp = end;
			}
		}
		else {
			int count{};
			for (int idx{ 0 }; idx <= end; idx++) {
				if (str[idx] == 'b')
					count++;
			}
			for (int idx{ start }; idx < str.length(); idx++) {
				if (str[idx] == 'b')
					count++;
			}
			if (count > bTemp) {
				bTemp = count;
				startTemp = start;
				endTemp = end;
			}
		}
		start++;
		end++;
		if (end == str.length())
			end = 0;
	}
	cout << bCount - bTemp;
}

int main() {
	string str;
	cin >> str;
	result(str);
}

void result

이 함수를 통해 문자열을 받고 위에서 정한 방법을 통해 문자열을 최소한으로 교환할 수 있는 부분 문자열을 찾아 결과를 출력했다.

 

문제후기

어려운 부분이 별로 없는 문제였다.