문제 설명
문자열 s가 하나 주어져 있다고 가정해 봅시다. s를 두 개의 비어 있지 않은 문자열 p와 q로 나누었을 때, p와 q를 이어 붙이면 다시 원래의 s가 되고, 동시에 p와 q에 포함된 서로 다른 문자(고유 문자)의 개수가 같다면, 이 분할을 '좋은 분할(good split)'이라고 합니다.
우리가 구해야 할 것은 문자열 s에서 만들 수 있는 좋은 분할의 총 개수입니다.
예를 들어 입력이 s = "xxzxyx"라면 출력은 2가 됩니다. 문자열을 나눌 수 있는 위치는 여러 곳이 있지만, ("xxz", "xyx") 또는 ("xxzx", "yx")처럼 나누는 경우에만 양쪽의 고유 문자 개수가 일치하기 때문입니다.
접근 방법
이 문제는 Counter(빈도 계산)를 두 개 사용하면 효율적으로 해결할 수 있습니다. 왼쪽 조각의 문자 빈도를 담는 맵과 오른쪽 조각의 문자 빈도를 담는 맵을 유지하면서, 문자열을 한 글자씩 왼쪽으로 옮겨 가며 매 시점 양쪽의 고유 문자 수를 비교하는 방식입니다.
구체적인 단계는 다음과 같습니다.
- result := 0으로 초기화합니다.
- left := 각 문자의 빈도를 세기 위한 빈 맵(딕셔너리)입니다.
- right := 문자열 s에 등장하는 모든 문자의 빈도를 미리 계산해 둔 맵입니다.
- s의 각 문자 c에 대해 아래를 반복합니다.
- left[c] 값을 1 증가시킵니다.
- right[c] 값을 1 감소시킵니다.
- right[c]가 0이 되면 right에서 해당 키를 삭제합니다.
- left와 right의 크기(서로 다른 문자의 종류 수)가 같으면 result를 1 증가시킵니다.
- 모든 반복이 끝나면 result를 반환합니다.
여기서 핵심은 맵의 '크기'가 곧 해당 조각에 포함된 고유 문자의 개수를 의미한다는 점입니다. 빈도가 0이 된 문자를 right에서 즉시 제거해 주어야 크기 비교가 정확하게 이루어집니다.
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
from collections import Counter
def solve(s):
result = 0
left, right = Counter(), Counter(s)
for c in s:
left[c] += 1
right[c] -= 1
if not right[c]:
del right[c]
if len(left) == len(right):
result += 1
return result
s = "xxzxyx"
print(solve(s))입력
"xxzxyx"
출력
2
동작 과정 살펴보기
s = "xxzxyx"의 경우, 커서가 한 글자씩 이동하면서 분할 지점을 검사합니다.
- 'x'를 왼쪽으로 옮긴 후 → left = {x}, right = {x, z, y} → 크기 1 vs 3, 불일치
- 'x'를 옮긴 후 → left = {x}, right = {x, z, y} → 크기 1 vs 3, 불일치
- 'z'를 옮긴 후 → left = {x, z}, right = {x, y} → 크기 2 vs 2, 일치 (count 1)
- 'x'를 옮긴 후 → left = {x, z}, right = {x, y} → 크기 2 vs 2, 일치 (count 2)
- 'y'를 옮긴 후 → left = {x, z, y}, right = {x} → 크기 3 vs 1, 불일치
- 'x'를 옮긴 후 → left = {x, z, y}, right = {} → 불일치
최종적으로 결과 값 2가 반환되며, 이는 ("xxz", "xyx")와 ("xxzx", "yx") 두 가지 좋은 분할에 해당합니다.
시간 및 공간 복잡도
- 시간 복잡도: O(n) — 문자열을 한 번만 순회하며, 각 단계의 맵 연산은 상수 시간에 처리됩니다.
- 공간 복잡도: O(k) — k는 문자열에 등장하는 고유 문자의 개수로, 두 개의 Counter에 저장됩니다.
이 방식은 가능한 모든 분할 지점마다 매번 새로 집합을 만들어 비교하는 순진한 O(n²) 접근보다 훨씬 효율적이며, 긴 문자열에서도 안정적인 성능을 보장합니다.