동종 부분 문자열이란?
주어진 문자열 s에서 동종(homogeneous) 부분 문자열의 총 개수를 구하는 문제입니다. 동종 문자열이란 문자열을 구성하는 모든 문자가 서로 동일한 경우를 의미합니다. 답이 매우 커질 수 있으므로 최종 결과는 10^9 + 7로 나눈 나머지를 반환해야 합니다.
예를 들어 입력 문자열이 s = "xyyzzzxx"라면 출력값은 13입니다. 해당 문자열에서 발견되는 동종 부분 문자열은 다음과 같습니다.
- "x" → 3회 등장
- "xx" → 1회 등장
- "y" → 2회 등장
- "yy" → 1회 등장
- "z" → 3회 등장
- "zz" → 2회 등장
- "zzz" → 1회 등장
따라서 (3 + 1 + 2 + 1 + 3 + 2 + 1) = 13이 됩니다.
해결 전략
이 문제의 핵심은 연속된 동일 문자 블록(run)을 식별하는 것입니다. 길이가 n인 연속된 동일 문자 블록에서 만들 수 있는 동종 부분 문자열의 개수는 1 + 2 + … + n = n × (n + 1) / 2개입니다.
예를 들어 "zzz"라는 블록 하나는 "z" 3개, "zz" 2개, "zzz" 1개로 총 6개(= 3 × 4 / 2)의 부분 문자열을 만들어냅니다.
문제 해결 절차는 다음과 같습니다.
- 문자열 끝에 "@"와 같은 센티널(sentinel) 문자를 붙여 마지막 문자 그룹도 손쉽게 처리할 수 있게 합니다.
- 문자열을 한 번 순회하면서 연속된 문자 그룹을 찾아 딕셔너리에 저장합니다.
- 저장된 각 고유 부분 문자열에 대해 길이 t에 따른 조합 수 t(t+1)/2를 계산합니다.
- 조합 수에 실제 등장 횟수를 곱해 모두 더합니다.
- 최종 합계를 10^9 + 7로 나눈 나머지를 반환합니다.
파이썬 구현 코드
def solve(s):
s += "@"
h = {}
prev = s[0]
c = 1
for i in s[1:]:
if prev != i:
if prev*c in h:
h[prev*c] += 1
else:
h[prev*c] = 1
c = 1
if prev == i:
c += 1
prev = i
fin = 0
for i in h:
t = len(i)
k = 0
while t != 0:
k += t
t -= 1
fin += k * h[i]
return fin % 1000000007
s = "xyyzzzxx"
print(solve(s))실행 결과
입력:
"xyyzzzxx"출력:
13더 효율적인 O(n) 풀이
위 방식은 딕셔너리를 사용하기 때문에 추가 메모리가 필요합니다. 사실 각 인덱스에서 현재까지 이어진 연속 문자의 길이를 바로 누적하면 공간 복잡도 O(1)로도 해결할 수 있습니다.
def solve(s):
ans = 0
count = 0
for i in range(len(s)):
if i > 0 and s[i] == s[i-1]:
count += 1
else:
count = 1
ans += count
return ans % 1000000007
s = "xyyzzzxx"
print(solve(s))여기서 count는 해당 인덱스를 끝점으로 하는 동종 부분 문자열의 개수를 의미합니다. 이 값을 모두 더하면 정답이 되며, 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 훨씬 효율적입니다.