[BOJ] #1759 - 암호 만들기

1759번: 암호 만들기

 

 

** 문제 유형

• 백트래킹

 

** 풀이

1. C개의 문자들이 주어졌을 때, 가능한 L 길이의 암호를 모두 찾아야 함
2. 따라서 C개의 문자들 중에서 L개를 선택하는 모든 조합을 고려
   • 파이썬의 조합(combinations) 라이브러리를 사용하면 간단히 해결 가능
   • 혹은 DFS를 이용하여 조합 함수 구현 가능

 

from itertools import combinations as comb

l, c = map(int, input().split())
array = list(input().split())

# 가능한 암호를 사전식으로 출력해야 하므로 정렬 수행
array.sort()

vowels = ['a', 'e', 'i', 'o', 'u']

# 길이가 l인 모든 암호 조합 확인
for pwd in list(map(''.join, comb(array, l))):
    cnt = 0

    # 모음의 개수 세기
    for i in pwd:
        if i in vowels:
            cnt += 1

    # 최소 한 개의 모음과 최소 2개의 자음이 있는 경우 출력
    if cnt >= 1 and cnt <= l - 2:
        print(pwd)