129. 암호 만들기

백준

1. Python

참고

L, C = map(int, input().split())
alpha = list(map(str, input().split()))
out = []
all_out = []
alpha.sort()

def solve(depth, idx, L, C):
    if depth == L: #N X M처럼 행을 내려가면서 탐색
        all_out.append(''.join(map(str, out)))
        #all_out.append(out[:])
        return
    for i in range(idx, C):
        out.append(alpha[i])
        solve(depth+1, i+1, L, C)
        out.pop()

def password(list_check):
    for i in list_check:
        cons = 0
        vow = 0
        for j in i:
            if j in 'aeiou':
                cons += 1
            else:
                vow += 1
        if cons >= 1 and vow >= 2:
            print(i)
    return

solve(0, 0, L, C)
password(all_out)

• 먼저 얻은 배열을 sort() 한다. (문자열 순으로도 됨) L자리의 암호 얻기 위해서 DFS를 적용,

  • 이 때 idx를 i+1을 넘겨주어 사전식으로 가능한 것들만 출력용 배열에 stack 한다.

• 출력용 배열에서 1개 이상의 모음 / 2개 이상의 자음을 검사하여 print 한다.

# cmd창

4 6
a t c i s w
함수 실행
out ['a']
재귀: solve(depth+1, i+1, L, C) 1 1 4 6
함수 실행
out ['a', 'c']
재귀: solve(depth+1, i+1, L, C) 2 2 4 6
함수 실행
out ['a', 'c', 'i']
재귀: solve(depth+1, i+1, L, C) 3 3 4 6
함수 실행
out ['a', 'c', 'i', 's']
재귀: solve(depth+1, i+1, L, C) 4 4 4 6
함수 실행
all_out ['acis']
out_pop ['a', 'c', 'i']
out ['a', 'c', 'i', 't']
재귀: solve(depth+1, i+1, L, C) 4 5 4 6
함수 실행
all_out ['acis', 'acit']
out_pop ['a', 'c', 'i']
out ['a', 'c', 'i', 'w']
재귀: solve(depth+1, i+1, L, C) 4 6 4 6
함수 실행
all_out ['acis', 'acit', 'aciw']
out_pop ['a', 'c', 'i']
out_pop ['a', 'c']
out ['a', 'c', 's']
재귀: solve(depth+1, i+1, L, C) 3 4 4 6
함수 실행
out ['a', 'c', 's', 't']
재귀: solve(depth+1, i+1, L, C) 4 5 4 6
함수 실행
all_out ['acis', 'acit', 'aciw', 'acst']
out_pop ['a', 'c', 's']
out ['a', 'c', 's', 'w']
재귀: solve(depth+1, i+1, L, C) 4 6 4 6
함수 실행
all_out ['acis', 'acit', 'aciw', 'acst', 'acsw']
out_pop ['a', 'c', 's'] #['a','c']에서 호출한 재귀 마지막 pop
out_pop ['a', 'c'] #재귀 호출한 ['a','c']의 pop
out ['a', 'c', 't']
재귀: solve(depth+1, i+1, L, C) 3 5 4 6
함수 실행
out ['a', 'c', 't', 'w']
재귀: solve(depth+1, i+1, L, C) 4 6 4 6
함수 실행
all_out ['acis', 'acit', 'aciw', 'acst', 'acsw', 'actw']
out_pop ['a', 'c', 't']
out_pop ['a', 'c']
out ['a', 'c', 'w']
재귀: solve(depth+1, i+1, L, C) 3 6 4 6
함수 실행
out_pop ['a', 'c']
out_pop ['a']
out ['a', 'i']
재귀: solve(depth+1, i+1, L, C) 2 3 4 6
함수 실행
out ['a', 'i', 's']
재귀: solve(depth+1, i+1, L, C) 3 4 4 6
함수 실행
out ['a', 'i', 's', 't']
재귀: solve(depth+1, i+1, L, C) 4 5 4 6
함수 실행
all_out ['acis', 'acit', 'aciw', 'acst', 'acsw', 'actw', 'aist']
out_pop ['a', 'i', 's']
out ['a', 'i', 's', 'w']
재귀: solve(depth+1, i+1, L, C) 4 6 4 6
함수 실행
all_out ['acis', 'acit', 'aciw', 'acst', 'acsw', 'actw', 'aist', 'aisw']
out_pop ['a', 'i', 's']
out_pop ['a', 'i']
out ['a', 'i', 't']
재귀: solve(depth+1, i+1, L, C) 3 5 4 6
함수 실행
out ['a', 'i', 't', 'w']
재귀: solve(depth+1, i+1, L, C) 4 6 4 6
함수 실행
all_out ['acis', 'acit', 'aciw', 'acst', 'acsw', 'actw', 'aist', 'aisw', 'aitw']
out_pop ['a', 'i', 't']
out_pop ['a', 'i']
out ['a', 'i', 'w']
재귀: solve(depth+1, i+1, L, C) 3 6 4 6
함수 실행
out_pop ['a', 'i']
out_pop ['a']
out ['a', 's']
재귀: solve(depth+1, i+1, L, C) 2 4 4 6
함수 실행
out ['a', 's', 't']
재귀: solve(depth+1, i+1, L, C) 3 5 4 6
함수 실행
out ['a', 's', 't', 'w']
재귀: solve(depth+1, i+1, L, C) 4 6 4 6
함수 실행
all_out ['acis', 'acit', 'aciw', 'acst', 'acsw', 'actw', 'aist', 'aisw', 'aitw', 'astw']
out_pop ['a', 's', 't']
out_pop ['a', 's']
out ['a', 's', 'w']
재귀: solve(depth+1, i+1, L, C) 3 6 4 6
함수 실행
out_pop ['a', 's']
out_pop ['a']
out ['a', 't']
재귀: solve(depth+1, i+1, L, C) 2 5 4 6
함수 실행
out ['a', 't', 'w']
재귀: solve(depth+1, i+1, L, C) 3 6 4 6
함수 실행
out_pop ['a', 't']
out_pop ['a']
out ['a', 'w']
재귀: solve(depth+1, i+1, L, C) 2 6 4 6
함수 실행
out_pop ['a']
out_pop []
out ['c']
재귀: solve(depth+1, i+1, L, C) 1 2 4 6
함수 실행
out ['c', 'i']
재귀: solve(depth+1, i+1, L, C) 2 3 4 6
함수 실행
out ['c', 'i', 's']
재귀: solve(depth+1, i+1, L, C) 3 4 4 6
함수 실행
out ['c', 'i', 's', 't']
재귀: solve(depth+1, i+1, L, C) 4 5 4 6
함수 실행
all_out ['acis', 'acit', 'aciw', 'acst', 'acsw', 'actw', 'aist', 'aisw', 'aitw', 'astw', 'cist']
out_pop ['c', 'i', 's']
out ['c', 'i', 's', 'w']
재귀: solve(depth+1, i+1, L, C) 4 6 4 6
함수 실행
all_out ['acis', 'acit', 'aciw', 'acst', 'acsw', 'actw', 'aist', 'aisw', 'aitw', 'astw', 'cist', 'cisw']
out_pop ['c', 'i', 's']
out_pop ['c', 'i']
out ['c', 'i', 't']
재귀: solve(depth+1, i+1, L, C) 3 5 4 6
함수 실행
out ['c', 'i', 't', 'w']
재귀: solve(depth+1, i+1, L, C) 4 6 4 6
함수 실행
all_out ['acis', 'acit', 'aciw', 'acst', 'acsw', 'actw', 'aist', 'aisw', 'aitw', 'astw', 'cist', 'cisw', 'citw']
out_pop ['c', 'i', 't']
out_pop ['c', 'i']
out ['c', 'i', 'w']
재귀: solve(depth+1, i+1, L, C) 3 6 4 6
함수 실행
out_pop ['c', 'i']
out_pop ['c']
out ['c', 's']
재귀: solve(depth+1, i+1, L, C) 2 4 4 6
함수 실행
out ['c', 's', 't']
재귀: solve(depth+1, i+1, L, C) 3 5 4 6
함수 실행
out ['c', 's', 't', 'w']
재귀: solve(depth+1, i+1, L, C) 4 6 4 6
함수 실행
all_out ['acis', 'acit', 'aciw', 'acst', 'acsw', 'actw', 'aist', 'aisw', 'aitw', 'astw', 'cist', 'cisw', 'citw', 'cstw']
out_pop ['c', 's', 't']
out_pop ['c', 's']
out ['c', 's', 'w']
재귀: solve(depth+1, i+1, L, C) 3 6 4 6
함수 실행
out_pop ['c', 's']
out_pop ['c']
out ['c', 't']
재귀: solve(depth+1, i+1, L, C) 2 5 4 6
함수 실행
out ['c', 't', 'w']
재귀: solve(depth+1, i+1, L, C) 3 6 4 6
함수 실행
out_pop ['c', 't']
out_pop ['c']
out ['c', 'w']
재귀: solve(depth+1, i+1, L, C) 2 6 4 6
함수 실행
out_pop ['c']
out_pop []
out ['i']
재귀: solve(depth+1, i+1, L, C) 1 3 4 6
함수 실행
out ['i', 's']
재귀: solve(depth+1, i+1, L, C) 2 4 4 6
함수 실행
out ['i', 's', 't']
재귀: solve(depth+1, i+1, L, C) 3 5 4 6
함수 실행
out ['i', 's', 't', 'w']
재귀: solve(depth+1, i+1, L, C) 4 6 4 6
함수 실행
all_out ['acis', 'acit', 'aciw', 'acst', 'acsw', 'actw', 'aist', 'aisw', 'aitw', 'astw', 'cist', 'cisw', 'citw', 'cstw', 'istw']
out_pop ['i', 's', 't']
out_pop ['i', 's']
out ['i', 's', 'w']
재귀: solve(depth+1, i+1, L, C) 3 6 4 6
함수 실행
out_pop ['i', 's']
out_pop ['i']
out ['i', 't']
재귀: solve(depth+1, i+1, L, C) 2 5 4 6
함수 실행
out ['i', 't', 'w']
재귀: solve(depth+1, i+1, L, C) 3 6 4 6
함수 실행
out_pop ['i', 't']
out_pop ['i']
out ['i', 'w']
재귀: solve(depth+1, i+1, L, C) 2 6 4 6
함수 실행
out_pop ['i']
out_pop []
out ['s']
재귀: solve(depth+1, i+1, L, C) 1 4 4 6
함수 실행
out ['s', 't']
재귀: solve(depth+1, i+1, L, C) 2 5 4 6
함수 실행
out ['s', 't', 'w']
재귀: solve(depth+1, i+1, L, C) 3 6 4 6
함수 실행
out_pop ['s', 't']
out_pop ['s']
out ['s', 'w']
재귀: solve(depth+1, i+1, L, C) 2 6 4 6
함수 실행
out_pop ['s']
out_pop []
out ['t']
재귀: solve(depth+1, i+1, L, C) 1 5 4 6
함수 실행
out ['t', 'w']
재귀: solve(depth+1, i+1, L, C) 2 6 4 6
함수 실행
out_pop ['t']
out_pop []
out ['w']
재귀: solve(depth+1, i+1, L, C) 1 6 4 6
함수 실행
out_pop []
acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw