문제 개요
영어 모음으로만 이루어진 문자열 s가 주어졌을 때, 가장 긴 '아름다운(beautiful)' 부분 문자열의 길이를 찾는 프로그램을 작성해 보겠습니다. 만약 조건을 만족하는 부분 문자열이 존재하지 않는다면 0을 반환해야 합니다.
문자열이 '아름다운' 문자열이 되려면 다음 두 가지 조건을 충족해야 합니다.
- 5개의 모음(a, e, i, o, u)이 각각 최소 한 번 이상 나타나야 합니다.
- 문자들이 알파벳 순서(a → e → i → o → u)로 정렬되어 있어야 합니다.
예를 들어 입력이 s = "aaioaaaaeiiouuooaauu"라면, 출력은 10입니다. 부분 문자열 "aaaaeiiouu"가 두 조건을 모두 만족하는 가장 긴 구간이기 때문입니다.
해결 알고리즘
이 문제는 투 포인터(two pointer) 기법을 활용하면 선형 시간 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 왼쪽 포인터 l과 오른쪽 포인터 r을 이용해 문자열을 모음 그룹 단위로 탐색하는 것입니다.
구체적인 동작 단계는 다음과 같습니다.
- 모든 모음을 순서대로 담은 리스트 vowels = ['a', 'e', 'i', 'o', 'u']를 준비합니다.
- l = 0, r = 0, longest = 0으로 초기화합니다.
- l이 문자열 길이보다 작은 동안 다음 과정을 반복합니다.
- valid를 True로 설정합니다.
- 각 모음에 대해 r이 가리키는 문자가 해당 모음과 일치하는지 검사하고, 일치하는 동안 r을 계속 앞으로 이동시킵니다. 이때 특정 모음이 한 번도 등장하지 않으면 valid는 False가 됩니다.
- valid가 True라면 5개 모음이 모두 알파벳 순서로 존재한다는 뜻이므로, longest를 longest와 (r - l) 중 더 큰 값으로 갱신합니다.
- l을 r로 옮겨 다음 구간 탐색을 준비합니다.
- 모든 탐색이 끝나면 longest를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 구현 과정을 더 자세히 살펴보겠습니다.
def solve(s):
vowels = ['a', 'e', 'i', 'o', 'u']
l, r, longest = 0, 0, 0
while (l < len(s)):
valid = True
for vowel in vowels:
valid &= (r < len(s) and s[r] == vowel)
while (r < len(s) and s[r] == vowel):
r += 1
if (valid):
longest = max(longest, r - l)
l = r
return longest
s = "aaioaaaaeiiouuooaauu"
print(solve(s))입력
"aaioaaaaeiiouuooaauu"
출력
10
동작 원리 살펴보기
입력 문자열 "aaioaaaaeiiouuooaauu"에서 첫 번째 그룹 "aaio"는 'u'가 없어 조건을 만족하지 못합니다. 반면 두 번째 그룹 "aaaaeiiouu"는 a, e, i, o, u가 모두 알파벳 순서로 등장하므로 길이 10의 아름다운 부분 문자열이 됩니다. 마지막 그룹 "ooaauu"는 모음 순서가 어긋나기 때문에 제외됩니다. 따라서 최종 결과는 10입니다.
복잡도 분석
포인터 r은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 추가로 사용하는 변수가 상수 개뿐이므로 공간 복잡도는 O(1)로, 매우 효율적인 해법입니다.