[BAEKJOON] 1522번 문자열 교환

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

 

문제조건

1. 와 b로만 이루어진 문자열이 주어질 때,  a를 모두 연속으로 만들기 위해서 필요한 교환의 최소 회수
2. 문자열은 원형이다.

접근방법

 

사실 투포인터 라기보다는 슬라이딩윈도우 방식의 풀이이다.

원형으로 이루어진 문자열이므로, 원형을 직선으로 펼친 배열로 보았을때, 모든 경우의수를 비교해서 최솟값을 찾는 방식으로 접근했다. 물론 주어진 문자열의 길이가 1000이므로, O(n^2)안에 탐색할수 있으므로 사용할수 있는 방법이다.

 

소스코드

#include <iostream>
#define MAX 1001
using namespace std;

string s;

int main() {
	cin >> s;
	int n = s.length();
	int res = n;
	int a = 0;
	for (int i = 0; i < n; i++)
		if (s[i] == 'a') a++;
	for (int i = 0; i < n; i++) {
		int tmp = a;
		int change = 0;
		for (int j = i; j < i + n; j++) {
			if (!tmp) break;
			if (s[j % n] == 'b') {
				change++;
				tmp--;
			}
			else tmp--;
		}
		res = min(res, change);
	}
	cout << res;
}

a를 기준으로 b를 만날때마다 연속되지 않은 a와 위치를 바꾸어주고, a가 모두 연속이 되면 최솟값을 계속 갱신한다.