[백준 1759] 암호 만들기

문제

L개의 알파벳 소문자로 구성되어 있는 암호가 있다.

암호는 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어야 한다. 그리고 암호는 알파벳이 증가하는 순서대로 배열되어 있다.

C개의 알파벳이 주어졌을 때 L개의 알파벳을 선택하여 만들 수 있는 암호를 출력하라

 

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

 

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

---

접근

백트래킹 연습을 위해 풀었다.

알파벳을 하나 선택할 때마다 모음과 자음을 카운트한다. 그리고 L개의 알파벳을 골랐을 때 문제의 조건에 부합된다면 출력하도록 구현하였다.

 

구현

알파벳을 입력받고 오름차순으로 정렬하였다.

그리고 모음에 해당하는 알파벳을 vowel이라는 리스트에 담아서 해당 알파벳이 모음인지 자음인지 구별하였다.

L, C = map(int, input().split())
alpha = list(map(str, input().split()))
alpha = sorted(alpha)
vowel = ['a', 'e', 'i', 'o', 'u']
solve(0, [], 0, 0)

 

재귀함수로 구현하였으며

먼저 선택을 할 때는 현재 알파벳이 모음인지 자음인지에 따라 다르게 재귀호출을 하였다. 모음일 때는 vow를 +1하여 넘기고 자음일 경우 cons를 +1하여 넘겼다.

 

이후 L개의 알파벳을 선택했을 때 모음이 1개 이상, 자음이 2개 이상일 경우 선택한 알파벳을 출력한다.

def solve(next, picked, vow, cons):
    if len(picked) == L:
        if vow > 0 and cons > 1:
            print(''.join(picked))
        return

    for i in range(next, C):
        if alpha[i] in vowel:
            picked.append(alpha[i])
            solve(i+1, picked, vow+1, cons)
        else:
            picked.append(alpha[i])
            solve(i+1, picked, vow, cons+1)
        picked.pop()

---

전체 코드

def solve(next, picked, vow, cons):
    if len(picked) == L:
        if vow > 0 and cons > 1:
            print(''.join(picked))
        return

    for i in range(next, C):
        if alpha[i] in vowel:
            picked.append(alpha[i])
            solve(i+1, picked, vow+1, cons)
        else:
            picked.append(alpha[i])
            solve(i+1, picked, vow, cons+1)
        picked.pop()

L, C = map(int, input().split())
alpha = list(map(str, input().split()))
alpha = sorted(alpha)
vowel = ['a', 'e', 'i', 'o', 'u']
solve(0, [], 0, 0)