[S1] 백준 1522번 문자열 교환 C++ 브루트포스 알고리즘, 슬라이딩 윈도우

리뷰

 

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

생각의 전환이 필요한 문제.. 그리디하게 접근하면 생각할게 너무 많다, 문자열의 길이가 최대 1000이니 그냥 완탐 돌리면 된다.

 

전역 변수

없음

 

 

함수

없음

 

 

문제풀이

1. 문자열 s를 입력 받고, 정수 n에 s의 길이를 저장한다.
2. a의 개수를 저장할 변수 a를 0으로 초기화 한다.
3. 정답을 저장할 변수 ans를 적당히 큰값으로 초기화 한다, 나는 10억으로 했다.
4. 문자열 s의 각 문자를 순회하며 a의 개수만큼 a를 증가시켜준다.
5. 다시 n번의 for문을 개행하고, b의 개수를 세어줄 정수형 변수 cnt를 0으로 초기화 한다.
6. i부터 i + a까지 탐색할 for문을 추가로 개행해 주고, s의 j % n번째 인덱스가 b라면 cnt를 증가시켜 준다.
7. 탐색을 마칠 때마다 ans와 cnt를 비교하여 최소값으로 ans를 갱신시켜 준다.

 

참고 사항

• 이 문제를 풀때 나처럼 b를 적재적소에 옮기고자 한다면 그 순간 함정에 빠지는 것이다.
• a의 개수를 세어주고, s의 특정 부분부터 a번째 길이까지 탐색했을때 b의 개수를 구해주면 된다.
• 만약 aaabbaabb일 경우 a의 개수는 5개이고, 어느 부분에서 탐색을 하더라도 b의 개수는 2개인 걸 알 수 있다.
• 따라서 b를 두번 옮겨줘야 온전히 a로만 이루어진 문자열을 만들 수 있다.

 

정답 코드

#include<iostream>
using namespace std;

int main() {
	string s; cin >> s;
	int n = s.size();
	int a = 0, ans = 1e9;
	for (int i = 0; i < n; i++) if (s[i] == 'a') a++;

	for (int i = 0; i < n; i++) {
		int cnt = 0;
		for (int j = i; j < i + a; j++) {
			if (s[j % n] == 'b') cnt++;
		}
		ans = min(ans, cnt);
	}
	cout << ans;
}