문제 소개
소문자로만 구성된 문자열 s가 주어졌을 때, 단 하나의 고유한 문자만 포함하는 부분 문자열(substring)의 총 개수를 구하는 것이 목표입니다.
예를 들어 입력 문자열이 "xxyy"라면, 조건을 만족하는 부분 문자열은 [x, x, xx, y, y, yy]로 총 6개이므로 결과값은 6이 됩니다.
해결 아이디어
핵심은 문자열을 왼쪽에서 오른쪽으로 한 글자씩 살펴보면서 같은 문자가 연속해서 나타나는 구간(run)의 길이를 추적하는 것입니다.
- 어떤 위치까지 같은 문자가 k번 연속되었다면, 그 위치를 끝으로 하는 유효한 부분 문자열은 정확히 k개입니다.
- 예를 들어 'xx'에서 두 번째 x에 도달했을 때 생성 가능한 부분 문자열은 [x, xx]의 2개입니다.
- 따라서 각 위치마다 현재 연속 길이를 누적하여 더하면 전체 개수를 구할 수 있습니다.
알고리즘을 순서대로 정리하면 다음과 같습니다.
- total := 0, previous := 빈 문자열로 초기화합니다.
- 문자열 s의 각 문자 c에 대해 반복합니다.
- c가 previous와 다르면 → previous := c로 갱신하고, 연속 길이(temp) := 1로 초기화합니다.
- c가 previous와 같으면 → temp := temp + 1로 증가시킵니다.
- total := total + temp를 수행합니다.
- 반복이 끝나면 total을 반환합니다.
구현 예제
class Solution:
def solve(self, s):
total = 0
previous = ''
for c in s:
if c != previous:
previous = c
in_a_row = 1
else:
in_a_row += 1
total += in_a_row
return total
ob = Solution()
print(ob.solve("xxyy"))
참고: total 누적 코드(total += in_a_row)는 if와 else 블록 바깥에 위치해야 합니다. 새로운 문자가 시작될 때도 연속 길이 1만큼은 부분 문자열이 생기기 때문입니다. 들여쓰기를 잘못하면 첫 글자의 카운트가 누락되어 오답이 나옵니다.
실행 결과 확인
입력
"xxyy"
출력
6
대안: groupby를 활용한 간결한 구현
파이썬 표준 라이브러리인 itertools.groupby를 사용하면 연속된 문자 구간을 손쉽게 묶을 수 있습니다. 길이가 n인 동일 문자 구간은 n × (n + 1) / 2개의 부분 문자열을 가지므로, 각 구간별로 이 공식을 적용해 더하면 됩니다.
from itertools import groupby
def count_unique_substrings(s):
total = 0
for _, group in groupby(s):
n = sum(1 for _ in group)
total += n * (n + 1) // 2
return total
print(count_unique_substrings("xxyy")) # 6
"xxyy"의 경우 'xx' 구간(n=2)에서 2×3÷2 = 3개, 'yy' 구간(n=2)에서 3개가 나와 합계 6이 됩니다.
복잡도 분석
- 시간 복잡도: O(N) — 문자열을 한 번만 순회합니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 몇 개의 변수만 사용합니다.