1759: 암호만들기

문제접근

전형적인 백트래킹 문제 유형이다. l, c 값과 알파벳을 받아오고, vowel(모음) 5개를 리스트에 넣어준 뒤, findPassword라는 재귀 함수를 만들어주었다. 이 함수의 로직을 간단히 설명하겠다.

1. 현재 만들어진 문자열(비밀번호)의 자음, 모음의 개수를 확인하고, 조건에 부합하지 않으면 return

2. 이 문자열(비밀번호)이 L과 같다면 해당 값을 arr에 담아줌

3. 제공된 문자열을 순회하며 자음, 모음 여부를 판단하고, 기존 문자열에 해당 문자를 추가해준 값과 함께 매개변수에 자,모음의 개수를 담아 재귀호출

 

첫번째 풀이(실패)

1. 작은 실수,, 시작하는 글자의 자음 or 모음 여부를 반영해주지 않았다..!(실제 풀이였다면 testcase에서 실수를 깨달았을 것 같아 큰 문제는 아닌 것 같다.)

2. len(password) == l 일 때 더 이상 순회할 필요가 없는데 return을 해주지 않았다. 

import sys

l, c = map(int, sys.stdin.readline().split())
inputValues = list(map(str, sys.stdin.readline().split()))
chars = sorted(inputValues)
vowel = ['a', 'e', 'i', 'o', 'u']
arr = []
def findPassword(password, con, vow):
    if con > l - 1 or vow > l - 2:
        return
    if len(password) == l:
        arr.append(password)

    for char in chars:
        if char in password or password[-1] > char:
            continue
        if char in vowel:
            findPassword(password + char, con, vow + 1)
        else:
            findPassword(password + char, con + 1, vow)


for char in chars:
    findPassword(char, 0, 0)
for i in arr:
    print(i)

두번째 풀이(성공)

위 언급한 실수를 수정하고 돌려보니 잘 동작한다. 

import sys

l, c = map(int, sys.stdin.readline().split())
inputValues = list(map(str, sys.stdin.readline().split()))
chars = sorted(inputValues)
vowel = ['a', 'e', 'i', 'o', 'u']
arr = []
def findPassword(password, con, vow):
    if con > l - 1 or vow > l - 2:
        return
    if len(password) == l:
        arr.append(password)
        return

    for char in chars:
        if char in password or password[-1] > char:
            continue
        if char in vowel:
            findPassword(password + char, con, vow + 1)
        else:
            findPassword(password + char, con + 1, vow)


for char in chars:
    if char in vowel:
        findPassword(char, 0, 1)
    else:
        findPassword(char, 1, 0)
for i in arr:
    print(i)