프로그래밍을 하다 보면 리스트에 담긴 여러 개의 문자열을 조합하여 원하는 문자열을 만들 수 있는지 확인해야 하는 경우가 종종 있습니다. 이때 리스트 내 문자열의 순서는 중요하지 않으며, 어떤 순서로 연결하더라도 목표 문자열이 완성되기만 하면 됩니다.
1. 순열(permutations)을 이용한 방법
파이썬의 itertools 모듈이 제공하는 permutations 함수를 사용하면 리스트에 있는 문자열들의 다양한 순서 조합을 모두 생성할 수 있습니다. 생성된 각 조합을 연결해 보면서 목표 문자열과 일치하는 순간, 해당 문자열을 만들 수 있다고 판단하면 됩니다.
예제 코드
from itertools import permutations
chk_str = 'balloon'
Alist = ['fly', 'on', 'o', 'hot', 'ball', 'air']
def findstring(strchk, biglist):
for i in range(2, len(biglist) + 1):
for perm in permutations(biglist, i):
if ''.join(perm) == strchk:
return True
return False
# 함수 사용
if findstring(chk_str, Alist):
print("문자열을 만들 수 있습니다.")
else:
print("문자열을 만들 수 없습니다.")
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
문자열을 만들 수 있습니다.
2. 정규 표현식을 이용한 방법
re 모듈의 compile 함수를 사용하면 리스트의 문자열들을 정규 표현식 패턴으로 지정하여 가능한 조합을 표현할 수 있습니다. 이 패턴으로 검사 대상 문자열을 매칭해 보고, 그 결과가 None이 아니라면 해당 문자열을 만들 수 있다고 결론지을 수 있습니다.
예제 코드
import re
chk_str = 'balloon'
Alist = ['fly', 'on', 'o', 'hot', 'ball', 'air']
def findstring(strchk, biglist):
r = re.compile("(?:" + "|".join(biglist) + ")*$")
if r.match(strchk) != None:
return True
return False
# 함수 사용
if findstring(chk_str, Alist):
print("문자열을 만들 수 있습니다.")
else:
print("문자열을 만들 수 없습니다.")
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
문자열을 만들 수 있습니다.
두 방법의 성능 및 동작 차이
- 성능: 순열 방식은 리스트의 길이가 늘어날수록 조합의 수가 계승(factorial) 단위로 폭발적으로 증가하므로, 요소가 많은 리스트에는 적합하지 않습니다. 반면 정규 표현식 방식은 패턴을 한 번 컴파일한 뒤 매칭만 수행하므로 훨씬 효율적입니다.
- 동작 방식: 위 정규 표현식 패턴은 각 단어를 여러 번 반복해서 사용할 수 있도록 허용합니다(
*연산자). 따라서 각 문자열 요소를 정확히 한 번씩만 사용해야 하는 제약이 필요하다면 순열 방식이 더 정확한 선택입니다.
요소 개수가 적고 엄격한 사용 규칙이 필요하다면 순열 방식을, 리스트가 크거나 성능이 중요하다면 정규 표현식 방식을 사용하는 것이 좋습니다.