문제 개요
문자열 s가 주어졌을 때, 이 문자열이 aⁿbⁿ 패턴을 따르는지 확인해야 합니다. aⁿbⁿ 패턴이란 문자 'a'가 n번 연속으로 나타난 뒤, 문자 'b'가 정확히 n번 연속으로 나타나는 형태를 의미합니다.
예를 들어 n = 3이라면 문자열은 "aaabbb"가 됩니다. 즉, 'a'의 개수와 'b'의 개수가 정확히 같아야 하며, 모든 'a'는 모든 'b'보다 앞에 위치해야 합니다.
따라서 입력이 s = "aaaaabbbbb"라면 이 문자열은 a⁵b⁵ 형태를 따르므로 결과는 True가 됩니다.
해결 전략
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- size := 문자열 s의 길이로 설정
- i를 0부터 size - 1까지 반복:
- s[i]가 'a'가 아니면 반복문을 종료(break)
- i × 2가 size와 같지 않으면 False 반환
(앞부분 'a'의 개수와 뒷부분 'b'의 개수가 같아야 하기 때문) - j를 i부터 size - 1까지 반복:
- s[j]가 'b'가 아니면 False 반환
- 모든 검사를 통과하면 True 반환
구현 코드
다음은 위 로직을 Python으로 구현한 예제입니다.
def solve(s):
size = len(s)
for i in range(size):
if s[i] != 'a':
break
if i * 2 != size:
return False
for j in range(i, size):
if s[j] != 'b':
return False
return True
s = "aaaaabbbbb"
print(solve(s))입력
"aaaaabbbbb"
출력
True
동작 원리 설명
첫 번째 반복문은 문자열 시작부터 연속된 'a'의 개수를 셉니다. 'a'가 아닌 문자를 만나는 순간 반복문이 중단되며, 이 시점의 인덱스 i는 'a' 블록의 길이가 됩니다.
그다음 i × 2 == size 조건을 확인하여 'a'의 개수가 전체 문자열 길이의 정확히 절반인지 검사합니다. 이 조건을 통과하지 못하면 'a'와 'b'의 개수가 같지 않으므로 패턴에서 벗어납니다.
마지막 두 번째 반복문은 나머지 부분이 모두 'b'로만 이루어져 있는지 확인합니다. 중간에 다른 문자가 섞여 있으면 False를 반환합니다.
시간 복잡도
두 반복문이 각각 최대 O(n)번 실행되므로 전체 시간 복잡도는 O(n)이며, 추가 공간 없이 수행되므로 공간 복잡도는 O(1)입니다.