문제 개요
문자열 s가 주어졌을 때, 이 문자열의 글자들로 만들 수 있는 모든 가능한 조합을 찾는 프로그램을 작성해야 합니다. 단, 다음과 같은 조건이 있습니다.
- 동일한 문자 집합을 가진 두 문자열이 존재한다면, 사전순(lexicographically)으로 가장 작은 것만 결과에 포함합니다.
- 문자열
s를 구성하는 각 문자는 모두 고유(unique)합니다.
입력 및 출력 예시
예를 들어 입력이 s = "pqr"이라면, 출력은 다음과 같습니다.
['r', 'qr', 'q', 'pr', 'pqr', 'pq', 'p']
해결 접근 방법
이 문제는 뒤에서부터 문자를 하나씩 처리하면서 기존 조합에 새로운 문자를 붙이는 방식으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.
- 빈 리스트
st_arr를 생성합니다. i를 문자열 길이 - 1부터 0까지 역순으로 반복합니다.j를 0부터 현재st_arr의 크기 - 1까지 반복하며,s[i]와st_arr[j]를 연결한 문자열을st_arr끝에 추가합니다.
- 각 반복이 끝나면
s[i]자체도st_arr에 추가합니다. - 모든 반복이 완료되면
st_arr를 반환합니다.
이 방식은 문자열의 뒤쪽 문자부터 시작해 앞쪽으로 진행하기 때문에, 자연스럽게 사전순으로 정렬된 순서에 가까운 결과를 얻을 수 있습니다.
파이썬 구현 코드
다음은 위 알고리즘을 실제로 구현한 예제입니다.
def solve(s):
st_arr = []
for i in range(len(s)-1,-1,-1):
for j in range(len(st_arr)):
st_arr.append(s[i]+st_arr[j])
st_arr.append(s[i])
return st_arr
s = "pqr"
print(solve(s))실행 결과 확인
입력:
"pqr"
출력:
['r', 'qr', 'q', 'pr', 'pqr', 'pq', 'p']
동작 원리 살펴보기
코드가 실행되는 과정을 단계별로 추적해 보면 다음과 같습니다.
- 첫 번째 반복(i=2): 리스트가 비어 있으므로 내부 반복은 실행되지 않고,
'r'만 추가됩니다. →['r'] - 두 번째 반복(i=1): 기존
'r'에'q'를 붙인'qr'을 추가하고,'q'자체도 추가합니다. →['r', 'qr', 'q'] - 세 번째 반복(i=0): 기존 세 요소 각각에
'p'를 붙인'pr','pqr','pq'를 추가하고, 마지막으로'p'를 추가합니다. →['r', 'qr', 'q', 'pr', 'pqr', 'pq', 'p']
시간 복잡도
길이가 n인 문자열의 부분집합 개수는 2ⁿ개이므로, 이 알고리즘의 시간 복잡도는 O(n × 2ⁿ)입니다. 문자열 길이가 커질수록 조합의 수가 지수적으로 증가한다는 점을 유의해야 합니다.