파이썬으로 문자열을 고유한 부분 문자열의 최대 개수로 분할하는 방법

문제 개요

문자열 s가 주어졌을 때, 이 문자열을 분할하여 만들 수 있는 고유한(중복되지 않는) 부분 문자열의 최대 개수를 구하는 프로그램을 작성해 보겠습니다.

문자열 s는 비어 있지 않은 부분 문자열들의 목록으로 분할할 수 있으며, 이 부분 문자열들을 순서대로 이어 붙였을 때 원래 문자열이 되어야 합니다. 단, 모든 부분 문자열은 서로 달라야 한다는 조건이 있습니다.

예를 들어 s = "pqpqrrr"인 경우 정답은 5입니다. ['p', 'q', 'pq', 'r', 'rr']처럼 분할하면 모든 부분 문자열이 고유하기 때문입니다. 반면 ['p', 'q', 'p', 'q', 'r', 'rr']처럼 분할하면 'p'와 'q'가 여러 번 등장하므로 유효하지 않습니다.

해결 방법: DFS 백트래킹

이 문제는 깊이 우선 탐색(DFS)을 활용한 백트래킹으로 해결할 수 있습니다. 전체 알고리즘은 다음과 같습니다.

res := 0만 담고 있는 리스트로 초기화합니다.
dfs(s, path) 함수를 정의합니다. path는 지금까지 선택한 부분 문자열을 저장하는 집합(set)입니다.
s가 빈 문자열이라면:
- res[0]을 res[0]과 path의 크기 중 더 큰 값으로 갱신한 뒤 반환합니다.
i를 1부터 s의 길이까지 순회하면서:
- x := s의 첫 i개 문자로 이루어진 접두사
- x가 path에 존재하지 않으면 dfs(s[i:], path ∪ {x})를 재귀 호출합니다.
메인 로직에서 dfs(s)를 호출한 후 res[0]을 반환합니다.

파이썬 코드 예시

다음 구현을 통해 동작 과정을 더 쉽게 이해할 수 있습니다.

def solve(s):
   res = [0]
   def dfs(s, path=set()):
      if not s:
         res[0] = max(res[0], len(path))
         return
      for i in range(1, len(s)+1):
         x = s[:i]
         if x not in path:
            dfs(s[i:], path|{x})
   dfs(s)
   return res[0]

s = "pqpqrrr"
print(solve(s))

입력

"pqpqrrr"

출력

동작 원리와 시간 복잡도

dfs 함수는 호출될 때마다 현재 문자열의 앞부분에서 길이 1부터 전체 길이까지 가능한 모든 접두사를 하나씩 잘라냅니다. 잘라낸 부분 문자열이 아직 사용되지 않았다면(path에 없다면) 집합에 추가하고, 남은 문자열에 대해 재귀적으로 탐색을 이어갑니다. 문자열을 끝까지 성공적으로 처리하면 해당 경로에서 사용된 서로 다른 부분 문자열의 개수를 res와 비교하여 최댓값을 갱신합니다.

이 풀이는 가능한 모든 분할 경우를 탐색하는 완전 탐색 방식이므로 시간 복잡도는 대략 지수 수준(약 O(2ⁿ))입니다. 따라서 문자열 길이가 짧게 제한되는 문제(예: n ≤ 16)에 적합하며, 실전 코딩 테스트에서도 이런 조건으로 출제되는 경우가 많습니다.