문제 개요
두 정수 A와 B가 주어졌을 때, 다음 조건을 모두 만족하는 임의의 문자열 S를 반환하는 것이 목표입니다.
- S의 길이는 A + B이며, 정확히 A개의 문자 'a'와 B개의 문자 'b'로 구성됩니다.
- 부분 문자열 "aaa"와 "bbb"는 S에 절대 나타나지 않아야 합니다.
예를 들어 A = 4, B = 1이 입력으로 주어지면, 유효한 출력은 "aabaa"입니다. 이 문자열은 'a' 4개와 'b' 1개를 포함하면서도 같은 문자가 세 번 연속으로 등장하지 않습니다.
풀이 전략
핵심 아이디어는 개수가 더 많은 문자를 우선적으로 배치하되, 두 문자의 개수 차이가 클 때는 "2개 + 1개" 패턴으로 묶어 배치하는 것입니다. 이렇게 하면 어떤 문자도 세 번 연속으로 놓이는 상황을 자연스럽게 피할 수 있습니다.
단계별 알고리즘
- 초기화: 빈 문자열 ret을 선언합니다.
- 1단계 — 개수 차이가 클 때: |A − B| ≥ 2인 동안 다음을 반복합니다.
- A > B인 경우: ret에 'aa'를 붙이고 A를 2 감소시킨 뒤, B가 남아 있으면 'b'를 하나 붙이고 B를 1 감소시킵니다.
- 그 외의 경우(B > A): ret에 'bb'를 붙이고 B를 2 감소시킨 뒤, A가 남아 있으면 'a'를 하나 붙이고 A를 1 감소시킵니다.
- 2단계 — 개수가 비슷할 때: A 또는 B 중 하나라도 남아 있는 동안 반복합니다. 문자열의 마지막 두 글자가 이미 'aa'로 끝나지 않는 한 'a'를 우선 추가하고, 이후 B가 남아 있으면 'b'를 함께 붙입니다. 그렇지 않으면 'b'를 추가하고 남은 'a'를 덧붙입니다.
- 반환: 완성된 문자열 ret을 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string strWithout3a3b(int A, int B) {
string ret = "";
while(abs(A - B) >= 2){
if(A > B){
ret += 'a';
ret += 'a';
A -= 2;
if(B) {
ret += 'b';
B--;
}
}else{
ret += 'b';
ret += 'b';
B -= 2;
if(A) {
ret += 'a';
A--;
}
}
}
while(A || B){
if(A && (ret.size() < 2 || !(ret.size() >= 2 && ret[ret.size() - 1] == ret[ret.size() - 2] && ret[ret.size() - 1] == 'a') ) ){
ret += 'a';
A--;
if(B) {
ret += 'b';
B--;
}
}else{
ret += 'b';
B--;
if(A) {
ret += 'a';
A--;
}
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.strWithout3a3b(4, 1));
}
입력
4
1
출력
"aabaa"
동작 원리 요약
첫 번째 while 루프는 두 문자 개수의 차이가 2 이상일 때, 많은 쪽 문자를 두 개씩 배치하고 적은 쪽 문자를 하나씩 섞어 넣어 균형을 맞춥니다. 두 번째 루프에서는 개수가 거의 비슷해진 상태에서 'a'와 'b'를 교대로 배치하며, 직전 두 글자가 'aa'인 경우에만 'b'를 먼저 추가하여 "aaa"가 생기는 것을 방지합니다. 이 방식은 시간 복잡도 O(A + B)로 문제를 효율적으로 해결합니다.