테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 암호 만들기 ======

===== 풀이 =====
  * n개 중에서 m개를 뽑는데, 알파벳 순으로만 뽑아야 한다면, 파이썬에서는 굳이 백트래킹으로 알파벳순이 아닌것을 가지치기할 필요없이 그냥 itertools.combinations를 쓰면 된다. 이러면 nCm개의 암호 후보를 뽑을수 있고, 이중에서 모음의 갯수만 조건에 맞는지 확인하면 된다. 이것은 O(m)에 가능하므로 총 시간 복잡도는 O(C(n,m)*m)이다. 백트래킹을 구현해서 글자 한개를 선택할때마다 모음의 갯수를 업데이트해주다면 O(m)부분을 없앨수 있지만, 전체 시간복잡도에 비교해보면 별 의미 없다.
  * 
===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1759. 암호 만들기".

- Problem link: https://www.acmicpc.net/problem/1759
- Solution link: http://www.teferi.net/ps/problems/boj/1759

Tags: [Backtracking]
"""

import itertools

VOWELS = {'a', 'e', 'i', 'o', 'u'}


def main():
    L, C = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    alphabets = input().split()

    for password in itertools.combinations(sorted(alphabets), L):
        vowel_count = sum(1 for ch in password if ch in VOWELS)
        if 1 <= vowel_count <= L - 2:
            print(''.join(password))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}