[Python] 백준 1759 - 암호만들기

백준 1759-암호만들기

문제

코드

import sys
from collections import deque
input= sys.stdin.readline

def find(v):
    global vlen, clen
    if len(password)==v:
        if vlen>0 and v-vlen>1:
            for i in range (v):
                print(password[i],end='')
            print()
            return
    for i in a:
        if i not in password:
            if len(password)==0 or i>password[len(password)-1]:
                if i in aeiou:
                    vlen+=1
                password.append(i)
                find(v)
                password.pop()
                if i in aeiou:
                    vlen -= 1

L, C= list(map(int, input().split()))
aeiou=['a', 'e', 'i', 'o','u']
alp=[]
password=deque()
a=input().split()
a.sort()

vlen=0
clen=0
find(L)

해설

백트래킹을 이용해서 풀었다.
(수학적으로 해결해 보려고 했지만 실패..)
1.모음, 자음 갯수 처리
aeiou=['a', 'e', 'i', 'o','u']을 만들어 모음 집합을 만들었다.
find 함수에서 append 할 때, i 가 모음집합 aeiou에 있을때, vlen을 1만큼 증가시켜 모음의 갯수를 카운트했다.
자음의 갯수는 L-vlen 이기 때문에 이것을 이용하여 카운트했다.
그리고 return하여 pop할때 vlen을 1만큼 감소시켜줬다.

2. 오름차순, 중복허용X
   if len(password)==0 or i>password[len(password)-1] 으로 중복허용을 피했다.