파이썬으로 선택 옵션이 있는 문자열의 모든 조합 생성하기

문제 개요

소문자 알파벳과 [, |, ] 같은 특수 문자로 이루어진 문자열 s가 있다고 가정해 보겠습니다. 여기서 [a|b|c]는 "a", "b", "c" 중 하나를 자유롭게 선택할 수 있음을 의미합니다. 우리의 목표는 문자열 s가 나타낼 수 있는 모든 가능한 값을 담은 리스트를 구하는 것입니다.

단, 두 가지 제약 조건이 있습니다.

대괄호 []는 서로 중첩될 수 없습니다.
대괄호 안의 선택지 개수에는 제한이 없습니다.

입력 예시

s = "[d|t|l]im[e|s]"

출력 예시

['dime', 'dims', 'lime', 'lims', 'time', 'tims']

첫 번째 대괄호에서 d, t, l 중 하나를, 두 번째 대괄호에서 e, s 중 하나를 선택하므로 총 3 × 2 = 6가지 조합이 만들어집니다.

해결 접근 방법: 백트래킹

이 문제는 백트래킹(Backtracking) 기법으로 깔끔하게 해결할 수 있습니다. 문자열을 왼쪽부터 순회하면서 일반 문자는 그대로 누적하고, 대괄호를 만나면 각 선택지마다 분기하여 재귀적으로 탐색합니다.

구체적인 알고리즘 단계는 다음과 같습니다.

문자열 s가 비어 있다면 빈 문자열 하나만 담은 리스트를 반환합니다.
n := 문자열 s의 길이, seq := 현재까지 만든 조각을 저장하는 리스트, res := 최종 결과 리스트로 초기화합니다.
재귀 함수 helper(pos)를 정의합니다.
- pos가 n과 같으면(문자열 끝에 도달하면) seq의 요소들을 이어 붙여 res에 추가합니다.
- s[pos:] 구간에 [가 존재하면:
  - start := pos + s[pos:]에서 [의 상대적 인덱스
  - end := pos + s[pos:]에서 ]의 상대적 인덱스
  - s[start+1:end]를 |로 분할한 각 선택지(option)에 대해:
    - seq에 s[pos:start](대괄호 앞부분)를 추가
    - seq에 option을 추가
    - helper(end + 1)을 재귀 호출
    - 백트래킹을 위해 seq에서 마지막 두 요소를 제거
- [가 더 이상 없다면 남은 문자열 전체(s[pos:])를 seq에 추가하고 helper(n)을 호출한 뒤 마지막 요소를 제거합니다.
메인 흐름에서 helper(0)을 호출합니다.
res를 사전순으로 정렬하여 반환합니다.

파이썬 구현 예제

class Solution:
    def solve(self, s):
        if not s:
            return [""]
        n = len(s)

        def helper(pos):
            if pos == n:
                res.append("".join(seq))
            else:
                if "[" in s[pos:]:
                    start = pos + s[pos:].index("[")
                    end = pos + s[pos:].index("]")
                    for option in s[start + 1 : end].split("|"):
                        seq.append(s[pos:start])
                        seq.append(option)
                        helper(end + 1)
                        seq.pop()
                        seq.pop()
                else:
                    seq.append(s[pos:])
                    helper(n)
                    seq.pop()

        seq = []
        res = []
        helper(0)
        return sorted(res)

ob = Solution()
s = "[d|t|l]im[e|s]"
print(ob.solve(s))

실행 결과

입력

"[d|t|l]im[e|s]"

출력

['dime', 'dims', 'lime', 'lims', 'time', 'tims']

동작 원리 살펴보기

위 코드의 핵심은 helper() 함수의 재귀 구조입니다.

일반 문자 구간 처리: 다음 대괄호가 나오기 전까지의 문자열 조각을 한 번에 seq에 넣어 불필요한 재귀 호출을 줄입니다.
선택 지점 분기: 대괄호를 만나면 내부의 선택지를 | 기준으로 나눈 뒤, 각 선택지마다 재귀 호출로 하위 탐색을 진행합니다.
상태 복원: 재귀 호출이 끝나면 pop()으로 seq를 원래 상태로 되돌려 다른 선택지를 탐색할 수 있게 합니다. 이것이 백트래킹의 핵심입니다.

시간 및 공간 복잡도

시간 복잡도: 각 대괄호의 선택지 개수를 곱한 전체 조합 수를 M, 문자열 길이를 N이라 할 때 약 O(M × N)입니다. 선택지가 많아질수록 조합 수는 기하급수적으로 증가합니다.
공간 복잡도: 재귀 호출 스택 깊이는 대괄호 개수에 비례하며, 결과 저장에 O(M × N)의 공간이 필요합니다.

마무리

이처럼 백트래킹을 활용하면 선택 옵션이 포함된 문자열의 모든 조합을 체계적으로 생성할 수 있습니다. 정규식 대체 패턴 확장, 테스트 케이스 자동 생성, 와일드카드 매칭 등 다양한 실무 시나리오에 응용할 수 있으니 코드를 직접 변형해 보며 감을 익혀 보시기 바랍니다.