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

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

아이디어

 

• 비밀번호의 모든 가능한 조합을 탐색해야 하므로 백트래킹을 사용
• 알파벳은 사전 순으로 정렬되어야 하므로 입력받은 알파벳 리스트를 정렬한 후 탐색을 시작
• 백트래킹 함수는 매개변수로 현재 인덱스를 받아 해당 인덱스 이후의 문자들만 탐색
• 패스워드의 길이가 L이면 해당 문자열이 유효한 비밀번호인지 check 함수를 통해 확인
  
  • 모음이 최소 1개
  • 자음이 최소 2개
• 조건을 만족하면 해당 비밀번호를 출력하고 만족하지 않으면 그대로 return

 

구현

import sys
input = sys.stdin.readline

def check(password):
    mo = sum (1 for x in password if x in 'aeiou')
    ja = len(password) - mo
    return mo >= 1 and ja >= 2

def back(idx, password):
    if len(password) == L:
        if check(password):
            print(password)
        return
    for i in range(idx, len(li)):
        password += li[i]
        back(i+1, password)
        password = password[:-1]


L, C = map(int, input().split())
li = list(input().split())

li = sorted(li)
back(0, "")

 

 

마무리

문제를 좀 잘 읽자 모음과 자음의 갯수 조건을 보지 않고 내 맘대로 풀다가 시간을 많이 날렸다.

막혔을땐 그냥 머리를 계속 박는 것보단 문제를 한번만 다시 읽어보는 것이 때로는 시간을 더 절약하는 방법일 수 있겠다.