길이가 짝수 n인 문자열 S가 있다고 가정해 보겠습니다. S에는 'a'와 'b' 두 종류의 문자만 포함되어 있습니다. 우리는 이 문자열을 수정하여 모든 길이의 접두사마다 문자 'a'와 'b'의 개수가 서로 같아지도록 만들려고 합니다. 이를 위해서는 문자열에서 임의의 위치를 선택하고 해당 위치의 문자를 반대 문자로 바꾸는 연산을 원하는 만큼 수행할 수 있으며, 최종적으로 수정된 문자열을 반환하면 됩니다.
예를 들어 입력이 S = "aabbbb"라면 출력은 "baabab"이 됩니다.
문제 해결 접근 방법
이 문제는 문자열을 두 글자씩 짝지어 확인하는 방식으로 간단하게 해결할 수 있습니다. 각 쌍에서 두 문자가 서로 같다면('aa' 또는 'bb') 그중 하나를 반대 문자로 바꿉니다. 그러면 모든 쌍이 정확히 'a' 한 개와 'b' 한 개를 가지게 되고, 짝수 길이의 모든 접두사는 이러한 완전한 쌍들로 구성되므로 자동으로 'a'와 'b'의 개수가 같아집니다. 참고로 홀수 길이의 접두사는 애초에 두 문자의 개수가 같을 수 없으므로 별도로 고려할 필요가 없습니다.
구체적인 해결 단계는 다음과 같습니다.
- 문자열의 길이 n을 구합니다.
- 인덱스 i를 0부터 시작하여 2씩 증가시키며 끝까지 순회합니다.
- S[i]와 S[i+1]이 서로 같으면 변경 횟수(ans)를 1 증가시키고, S[i]를 반대 문자('a'라면 'b', 아니라면 'a')로 바꿉니다.
- 순회가 끝나면 수정된 문자열 S를 반환합니다.
n := size of S for initialize i := 0, when i < n, update i := i + 2, do: if S[i] is same as S[i + 1], then: (increase ans by 1) S[i] := (if S[i] is same as 'a', then 'b', otherwise 'a') return S
예제 코드
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
string solve(string S){
int n = S.size(), ans = 0;
for (int i = 0; i < n; i += 2)
if (S[i] == S[i + 1]){
ans++;
S[i] = S[i] == 'a' ? 'b' : 'a';
}
return S;
}
int main(){
string S = "aabbbb";
cout << solve(S) << endl;
}입력
"aabbbb"
출력
baabab
실행 결과 "aabbbb"가 "baabab"으로 변경되었습니다. 실제로 결과 문자열의 짝수 길이 접두사를 확인해 보면 길이 2의 "ba", 길이 4의 "baab", 길이 6의 "baabab" 모두 'a'와 'b'가 각각 절반씩 포함되어 있는 것을 알 수 있습니다.