[백준] 1759번: 암호 만들기 파이썬

https://www.acmicpc.net/problem/1759

 

백트레킹 이라는 거?

백트래킹으로 푸는 문제.

모음이 최소 한번, 자음이 최소 두번 들어가게 만들어야하는데

이걸 어렵게 생각하다가

생각 보다 간단하게 그냥 갯수 세는 식으로 구현하면 되겠구나 해서 바로 풀었다.

풀이

import sys

def func(k):
  global vowel, consonant
  if k == 0:
    vowel =0
    consonant = 0
  if k == l and vowel>0 and consonant >1:
    for i in range(l):
      print(password[i], end = '')
    print('')
    return 0 
  for i in range(c):
    if not isused[i] and (k == 0 or password[k-1] < c_list[i]):
      if c_list[i] in vowels:
        vowel += 1
      else:
        consonant += 1
      password[k] = c_list[i]
      isused[i] = True
      func(k+1)
      if c_list[i] in vowels:
        vowel -= 1
      else:
        consonant -= 1
      isused[i] = False

l, c = map(int, sys.stdin.readline().split())
c_list = list(map(str, sys.stdin.readline().split()))
c_list.sort()
vowels = ['a', 'e', 'i', 'o', 'u']
password = [0] * 15
isused = [False] * 15
vowel =0
consonant = 0
func(0)

 

구현을 패스워드 한글자 추가 할때마다 자음인지 모음인지 확인하고 카운트해서

패스워드 길이가 l이 되었을때 카운트된 숫자가 모음최소1개, 자음 최소2개 확인하게 구현했는데

 

지금 생각 해보니 그냥 패스워드길이 l 되었을때 for문으로 자음모음개수 바로 세는 게 나은 방법같다....