문제 개요
문자열 s와 정수 r이 주어졌을 때, 문자열 s에서 r개의 문자를 선택해 만들 수 있는 모든 순열(permutation)을 출력하는 프로그램을 작성해야 합니다.
파이썬에서는 표준 라이브러리인 itertools 모듈에 포함된 permutations() 함수를 사용하면 이 작업을 아주 간단하게 처리할 수 있습니다. 이 함수는 반복 가능한 객체와 길이 r을 인자로 받아, 해당 길이의 모든 순열을 튜플(tuple) 형태로 차례대로 반환합니다.
예를 들어 입력이 s = "HELLO", r = 3이라면 출력은 다음과 같습니다.
['HEL', 'HEL', 'HEO', 'HLE', 'HLL', 'HLO', 'HLE', 'HLL', 'HLO', 'HOE',
'HOL', 'HOL', 'EHL', 'EHL', 'EHO', 'ELH', 'ELL', 'ELO', 'ELH', 'ELL',
'ELO', 'EOH', 'EOL', 'EOL', 'LHE', 'LHL', 'LHO', 'LEH', 'LEL', 'LEO',
'LLH', 'LLE', 'LLO', 'LOH', 'LOE', 'LOL', 'LHE', 'LHL', 'LHO', 'LEH',
'LEL', 'LEO', 'LLH', 'LLE', 'LLO', 'LOH', 'LOE', 'LOL', 'OHE', 'OHL',
'OHL', 'OEH', 'OEL', 'OEL', 'OLH', 'OLE', 'OLL', 'OLH', 'OLE', 'OLL']
출력 결과에 중복된 값들이 보이는데, 이는 permutations() 함수가 문자 자체가 아니라 위치(인덱스) 기준으로 순열을 생성하기 때문입니다. "HELLO"에는 'L'이 두 개 있으므로, 서로 다른 위치의 'L'을 사용한 순열은 값이 같더라도 별도의 결과로 생성됩니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
vals:itertools.permutations()를 사용해s에서 길이r인 모든 순열을 리스트로 저장합니다.res: 최종 결과를 담을 새로운 빈 리스트를 생성합니다.vals의 각 요소x(문자들의 튜플)에 대해join()메서드로 하나의 문자열로 변환한 뒤res에 추가합니다.res를 반환합니다.
구현 예시
아래 코드를 통해 실제 동작 과정을 확인해 보겠습니다.
from itertools import permutations
def solve(s, r):
vals = list(permutations(s, r))
res = []
for x in vals:
res.append(''.join(x))
return res
s = "HELLO"
r = 3
print(solve(s, r))
입력
"HELLO", 3
출력
['HEL', 'HEL', 'HEO', 'HLE', 'HLL', 'HLO', 'HLE', 'HLL', 'HLO', 'HOE',
'HOL', 'HOL', 'EHL', 'EHL', 'EHO', 'ELH', 'ELL', 'ELO', 'ELH', 'ELL',
'ELO', 'EOH', 'EOL', 'EOL', 'LHE', 'LHL', 'LHO', 'LEH', 'LEL', 'LEO',
'LLH', 'LLE', 'LLO', 'LOH', 'LOE', 'LOL', 'LHE', 'LHL', 'LHO', 'LEH',
'LEL', 'LEO', 'LLH', 'LLE', 'LLO', 'LOH', 'LOE', 'LOL', 'OHE', 'OHL',
'OHL', 'OEH', 'OEL', 'OEL', 'OLH', 'OLE', 'OLL', 'OLH', 'OLE', 'OLL']
참고 사항
만약 중복 없는 고유한 순열만 필요하다면, 결과를 set(res)로 변환하거나 sorted(set(res))를 사용해 정렬된 고유 값 리스트를 얻을 수 있습니다. 또한 순열의 개수는 nPr = n! / (n−r)! 공식으로 계산되므로, 입력 문자열이 길어질 경우 결과의 크기가 급격히 커진다는 점을 유의해야 합니다.