파이썬으로 연속된 'a' 그룹 뒤에 같은 길이의 'b' 그룹이 오는지 확인하는 방법

문제 개요

소문자로만 구성된 문자열 s가 주어지며, 이 문자열에는 'a'와 'b' 두 가지 문자만 포함되어 있다고 가정해 보겠습니다. 이때 우리가 확인해야 할 것은 모든 연속된 'a' 그룹 바로 뒤에 동일한 길이의 연속된 'b' 그룹이 따라오는지 여부입니다.

예를 들어 입력 문자열이 s = "abaaabbbaabbaabbab"이라면 결과는 True입니다. 전체 문자열을 그룹으로 나누면 (ab), (aaabbb), (aabb), (aabb), (ab)가 되는데, 각 'a' 그룹과 'b' 그룹의 길이가 서로 일치하기 때문입니다.

해결 접근 방식

이 문제는 카운터 변수 하나만으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

'a'를 만날 때마다 카운터를 1씩 증가시킵니다.
'b'를 만날 때마다 카운터를 1씩 감소시킵니다.
각 그룹 쌍이 끝날 때마다 카운터가 0이 아니라면, 'a'와 'b'의 개수가 맞지 않는 것이므로 False를 반환합니다.

구체적인 알고리즘 단계는 다음과 같습니다.

카운터 a_count := 0, 문자열 길이 string_len := len(s)로 초기화합니다.
인덱스 i := 0으로 설정합니다.
i < string_len인 동안 다음을 반복합니다.
- 현재 문자가 'a'인 동안 a_count를 증가시키고 i를 앞으로 이동합니다.
- 현재 문자가 'b'인 동안 a_count를 감소시키고 i를 앞으로 이동합니다.
- 이 시점에서 a_count가 0이 아니라면 False를 반환합니다.
모든 검사를 통과하면 True를 반환합니다.

구현 예제

아래 파이썬 코드를 통해 위 알고리즘을 직접 확인해 보겠습니다.

def solve(s):
    a_count = 0
    string_len = len(s)
    i = 0
    while i < string_len:
        while i < string_len and s[i] == 'a':
            a_count += 1
            i += 1
        while i < string_len and s[i] == 'b':
            a_count -= 1
            i += 1
        if a_count != 0:
            return False
    return True

s = "abaaabbbaabbaabbab"
print(solve(s))

입력

"abaaabbbaabbaabbab"

출력

True

코드 설명 및 복잡도 분석

이 알고리즘은 문자열을 한 번만 순회하면서 각 그룹 내에서 'a'와 'b'의 개수 균형을 실시간으로 검증합니다. 'a' 그룹이 끝나고 'b' 그룹이 처리된 직후 카운터가 0이 되어야 하며, 그렇지 않으면 두 그룹의 길이가 다르다는 의미이므로 즉시 False를 반환합니다.

시간 복잡도: O(n) — 문자열의 각 문자를 정확히 한 번씩만 방문합니다.
공간 복잡도: O(1) — 추가적인 자료 구조 없이 단일 카운터 변수만 사용합니다.

이처럼 단순한 카운팅 기법만으로도 그룹 길이 대칭성 문제를 선형 시간 안에 해결할 수 있습니다.