Python에서 주어진 문자열을 4개의 고유한 부분 문자열로 분할할 수 있는지 확인하는 방법

문제 개요

문자열 s가 주어졌을 때, 이 문자열을 비어 있지 않고 서로 모두 다른(고유한) 4개의 부분 문자열로 나눌 수 있는지 확인하는 문제입니다.

예를 들어 입력이 s = "helloworld"라면, ["hel", "lo", "wor", "ld"]와 같이 네 조각으로 나눌 수 있으므로 결과는 True가 됩니다.

해결 접근 방식

이 문제는 다음 두 가지 아이디어로 해결할 수 있습니다.

• 길이가 10 이상인 경우: 문자열을 길이가 각각 1, 2, 3, n−6(≥ 4)이 되도록 잘라내면 네 조각의 길이가 모두 다릅니다. 길이가 다른 문자열은 절대 같을 수 없으므로, 이 경우 항상 True를 반환해도 됩니다.
• 그 외의 경우(길이 9 이하): 세 개의 자르는 위치 i, j, k를 완전 탐색(brute force)하면서, 만들어지는 네 개의 부분 문자열이 서로 모두 다른지 하나씩 검사합니다.

알고리즘 단계

• 문자열 s의 길이가 10 이상이면 True를 반환합니다.
• i를 1부터 len(s) − 1까지 순회하면서:
  • j를 i + 1부터 len(s) − 1까지 순회하면서:
    • k를 j + 1부터 len(s) − 1까지 순회하면서:
      • sub1 := s[0:i]
      • sub2 := s[i:j]
      • sub3 := s[j:k]
      • sub4 := s[k:]
      • 네 부분 문자열이 모두 서로 다르면 True를 반환합니다.
• 모든 경우를 확인한 후에도 찾지 못했다면 False를 반환합니다.

구현 예제

다음 코드는 위 알고리즘을 파이썬으로 구현한 것입니다. 네 부분 문자열을 집합(set)에 넣어 개수를 확인하면, 일일이 쌍으로 비교하는 것보다 훨씬 간결하게 중복 여부를 판별할 수 있습니다.

def solve(s):
    if len(s) >= 10:
        return True
    for i in range(1, len(s)):
        for j in range(i + 1, len(s)):
            for k in range(j + 1, len(s)):
                sub1 = s[:i]
                sub2 = s[i:j]
                sub3 = s[j:k]
                sub4 = s[k:]
                if len({sub1, sub2, sub3, sub4}) == 4:
                    return True
    return False

s = "helloworld"
print(solve(s))

입력

"helloworld"

출력

True

복잡도 분석

• 시간 복잡도: 세 개의 자르는 위치를 탐색하는 삼중 반복문이 사용되므로 O(n³)이며, 슬라이싱 비용까지 고려하면 최악의 경우 O(n⁴)입니다. 다만 길이가 10 이상인 입력은 상수 시간에 처리되므로 실제 탐색 범위는 길이 9 이하로 제한됩니다.
• 공간 복잡도: 부분 문자열을 저장하기 위해 O(n)의 추가 공간이 필요합니다.