https://www.acmicpc.net/problem/1759
바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.
암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.
새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.
접근 방법: DFS, 백트래킹
import sys
vowel = {'a', 'e', 'i', 'o', 'u'}
letters, candidates = map(int, sys.stdin.readline().strip().split())
char_list = sys.stdin.readline().strip().split()
char_list.sort()
tmp = []
def isValid(pw):
pw = set(pw)
return True if len(pw & vowel) and len(pw - vowel) >= 2 else False
def dfs(start, letters):
if letters == 0:
if isValid(tmp): print(''.join(tmp))
return
for i in range(start, candidates):
tmp.append(char_list[i])
dfs(i + 1, letters - 1)
tmp.pop()
dfs(0, letters)-
사전순으로 나열하여야 하므로 우선 들어온
char_list를 정렬해준다. -
이 전에
combinations를 만드는 문제에서 사용한 방법대로 전체 문자 리스트에서 문자 조합을 만들고, 문자 조합이 만들어지면isValid()를 통과시켜 주어진 조건에 문자 조합이 부합하는지 확인하는 식으로 구현하였다. -
모음이 하나 이상, 자음이 둘 이상 필요하므로 모음이 담긴
vowel세트를 만들어 주어isValid()를 작성하였다. -
재귀함수를 돌며
char_list앞에서부터 하나씩 문자를 가져오고, 그 문자를 제외한 나머지char_list를 다음 재귀함수로 넘겨주면서 원하는 길이의 문자 조합이 나올 때 까지 재귀함수를 돈다.
import itertools
def password():
combinations = itertools.combinations(char_list, 4)
for c in combinations:
if isValid(c):
print(''.join(c))
password()- 혹은 전에 사용하였던
itertools모듈을 이용해itertools.combinations메소드를 이용하면 위의 방식으로 구현한 것 보다 쉽고 빠르게 문자 조합을 구할 수 있다. 구한 문자 조합을 앞부터 하나씩 순회하면서isValid()에 통과시킨 후 프린트하면 된다.
