문제 설명
소문자로만 구성된 문자열 s가 주어졌을 때, s의 모든 부분 문자열에 대해 각 부분 문자열 안에서 한 번만 등장하는(고유한) 문자의 개수를 모두 더한 값을 구해야 합니다. 결과가 매우 커질 수 있으므로 10⁹+7로 나눈 나머지를 반환합니다.
예를 들어 s = "xxy"라면 정답은 6입니다. 각 부분 문자열과 그 기여도는 다음과 같습니다.
- "x" : 1
- "x" : 1
- "y" : 1
- "xx" : 0 — 'x'가 두 번 등장하므로 고유하지 않음
- "xy" : 2
- "xxy" : 1 — 'x'는 고유하지 않고 'y'만 계산됨
전체 합계는 1 + 1 + 1 + 0 + 2 + 1 = 6입니다.
핵심 아이디어: 문자별 기여도 계산
모든 부분 문자열을 일일이 만들어 검사하면 O(n²)개의 부분 문자열을 처리해야 해서 비효율적입니다. 대신 관점을 바꿔 "각 문자 위치가 몇 개의 부분 문자열에서 고유하게 등장하는가?"를 계산하면 선형 시간에 문제를 해결할 수 있습니다.
문자열에서 어떤 문자 symbol이 인덱스 i에 있을 때, 왼쪽에서 가장 가까운 동일 문자의 위치를 left, 오른쪽에서 가장 가까운 동일 문자의 위치를 right라고 합시다. 이때 이 위치의 문자가 유일하게 포함되는 부분 문자열의 개수는 다음과 같습니다.
cnt = (i − left) × (right − i)
부분 문자열의 시작 위치는 (left, i] 사이에서 (i − left)가지 고를 수 있고, 끝 위치는 [i, right) 사이에서 (right − i)가지 고를 수 있기 때문입니다.
알고리즘 단계
- m := 10⁹ + 7 (나머지 연산용 모듈러 값)
- prev_seen := 각 문자의 등장 위치 목록을 담는 빈 딕셔너리
- ans := 0
- util(i, symbol) 함수를 정의합니다.
- prev_seen[symbol]이 없으면 [-1]로 초기화합니다(문자열 시작 경계 처리).
- 현재 인덱스 i를 prev 리스트의 끝에 추가합니다.
- prev의 길이가 3보다 크면:
- left := prev의 첫 번째 원소를 꺼내고(pop) 제거
- middle := prev[0], right := prev[1]
- cnt := (middle − left) × (right − middle)
- ans := (ans + cnt) mod m
- s의 각 인덱스 i와 문자 symbol에 대해 util(i, symbol)을 호출합니다.
- 마지막으로 모든 문자에 대해 util(len(s), symbol)을 호출해 문자열 끝 경계를 처리합니다.
- ans를 반환합니다.
초기 값 [-1]과 마지막에 len(s)를 넣어주는 처리 덕분에 문자열 양 끝의 경계 조건이 자연스럽게 반영됩니다.
구현 예제
class Solution:
def solve(self, s):
m = 10 ** 9 + 7
prev_seen = {}
ans = 0
def util(i, symbol):
nonlocal ans
prev = prev_seen.setdefault(symbol, [-1])
prev.append(i)
if len(prev) > 2:
left = prev.pop(0)
middle, right = prev
cnt = (middle - left) * (right - middle)
ans = (ans + cnt) % m
for i, symbol in enumerate(s):
util(i, symbol)
for symbol in prev_seen:
util(len(s), symbol)
return ans
ob = Solution()
s = "xxy"
print(ob.solve(s))
입력
xxy
출력
6
복잡도 분석
이 알고리즘은 문자열의 각 문자를 한 번씩만 처리하므로 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 각 문자의 등장 위치를 저장하므로 O(n)입니다. 모든 부분 문자열을 직접 탐색하는 브루트포스 방식(O(n²) 이상)에 비해 훨씬 효율적입니다.