'a'와 'b' 두 문자로만 구성된 문자열이 주어졌을 때, 이 문자열이 aⁿbⁿ 형태를 만족하는지 판별하는 문제입니다. 즉, n개의 'a' 뒤에 정확히 n개의 'b'가 이어지는 구조인지 확인해야 합니다. 조건을 만족하면 1(true)을, 그렇지 않으면 0(false)을 반환합니다.
예를 들어 입력 문자열이 "aaaaaaaaaaaabbbbbbbbbbbb"라면, 앞부분에 12개의 'a'가 있고 뒷부분에 동일하게 12개의 'b'가 이어지므로 결과는 true(1)가 됩니다.
문제 해결 접근 방식
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 입력 문자열의 전체 길이를 구합니다.
- 문자열 처음부터 순회하며 연속된 'a'의 개수를 셉니다. 'a'가 아닌 문자를 만나면 해당 지점에서 반복문을 종료합니다.
- 'a'의 개수(i)에 2를 곱한 값이 전체 길이와 일치하지 않으면 false를 반환합니다. 이는 'a'와 'b'의 개수가 정확히 같아야 한다는 핵심 조건을 검사하는 과정입니다.
- 'a'가 끝난 지점부터 문자열 끝까지 순회하며 나머지 문자가 모두 'b'인지 확인하고, 'b'가 아닌 문자가 하나라도 있으면 false를 반환합니다.
- 모든 조건을 통과하면 true를 반환합니다.
C++ 예제 코드
아래 예제 코드를 통해 구현 방법을 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
bool solve(string input_string) {
int length = input_string.length();
int i;
for (i = 0; i < length; i++)
if (input_string[i] != 'a')
break;
if (i * 2 != length)
return false;
for (int j = i; j < length; j++)
if (input_string[j] != 'b')
return false;
return true;
}
int main() {
string input_string = "aaaaaaaaaaaabbbbbbbbbbbb";
cout << solve(input_string)<< endl;
return 0;
}입력
"aaaaaaaaaaaabbbbbbbbbbbb"
출력
1
위 알고리즘은 문자열을 최대 두 번 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 문제를 효율적으로 해결할 수 있습니다. 첫 번째 반복문이 첫 번째 비-'a' 문자에서 멈추기 때문에 'a'가 모두 연속되어 있다는 점도 자연스럽게 보장됩니다.