소문자로만 구성된 문자열 s가 주어졌을 때, 각 모음(a, e, i, o, u)이 모두 짝수 번 등장하는 가장 긴 부분 문자열(substring)의 길이를 찾는 문제를 풀어보겠습니다.
예를 들어 입력이 s = "anewcoffeepot"이라면 결과는 10입니다. 부분 문자열 "wcoffeepot"에는 모음 'o'와 'e'만 포함되며, 두 모음이 각각 정확히 두 번씩 등장하기 때문입니다.
접근 방법: 비트마스크(Bitmask) 활용
모음은 총 5개이므로, 5비트짜리 비트마스크를 사용하면 각 모음의 등장 횟수 홀짝성(패리티)을 하나의 정수로 표현할 수 있습니다. 비트 연산 XOR(^)을 사용하면 같은 모음을 다시 만날 때마다 해당 비트가 뒤집혀, 결국 동일한 마스크 값이 두 번 나타났다는 것은 그 사이 구간에서 모든 모음이 짝수 번 등장했다는 의미가 됩니다.
알고리즘 단계
- 모음과 숫자 값을 매핑합니다: a→0, e→1, i→2, o→3, u→4
- prefix라는 딕셔너리를 만들고 초기값 {0: -1}을 저장합니다.
- mask = 0, n = 문자열 길이, res = 0으로 초기화합니다.
- i를 0부터 n-1까지 반복하면서:
- s[i]가 모음이면 mask를 해당 비트와 XOR 연산합니다.
- mask가 prefix에 없다면 prefix[mask] = i로 기록합니다.
- mask가 이미 prefix에 있다면 res를 max(res, i - prefix[mask])로 갱신합니다.
- 반복이 끝나면 res를 반환합니다.
구현 예제
class Solution:
def solve(self, s):
vowels = {"a": 0, "e": 1, "i": 2, "o": 3, "u": 4}
prefix = {0: -1}
mask = 0
n = len(s)
res = 0
for i in range(n):
if s[i] in vowels:
mask ^= 1 << vowels[s[i]]
if mask not in prefix:
prefix[mask] = i
else:
res = max(res, i - prefix[mask])
return res
ob = Solution()
s = "anewcoffeepot"
print(ob.solve(s))입력
"anewcoffeepot"
출력
10
동작 원리 설명
prefix 딕셔너리에는 각 마스크 값이 처음 등장한 인덱스가 저장됩니다. 초기값 {0: -1}이 있는 이유는, 문자열 시작부터 어떤 위치까지의 구간도 고려하기 위함입니다. 동일한 마스크가 다시 나타나면 두 인덱스 사이의 모든 모음 개수가 짝수임이 보장되므로, 그 차이가 곧 후보 답이 됩니다.
이 방법의 시간 복잡도는 O(n), 공간 복잡도는 최대 32가지 마스크 상태만 존재하므로 O(1)로 매우 효율적입니다. 단순히 모든 부분 문자열을 검사하는 브루트 포스 방식(O(n²) 이상)과 비교하면 큰 성능 향상을 얻을 수 있습니다.