[백준 1759] 암호 만들기

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

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

출력

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

---

풀이

구하고자 하는 것을 정리해보면,

한 개의 모음과 두 개의 자음이 포함된 L개의 문자로 이루어진 오름차순 수열이다

 

먼저 재귀 내부에 반복문을 통해 수열을 구성하는 방법은 O(N!)이 걸리므로, 최댓값이 15인 L값을 고려하면 시간 내에 불가능해보인다

각 문자를 채택하거나 채택하지 않는 O(2^n) 방법을 써보기로 했다

 

1. 문제 조건 중 "증가하는 순서"를 구성하기 위해 입력받은 문자들을 오름차순으로 정렬

 

2. 재귀함수로 L개의 문자로 구성된 수열을 반복 생성

 

3. 한 개의 모음과 두 개의 자음 조건을 충족시키기 위해 수열 내에 한 개의 모음이 있는지 확인 (L의 최솟값은 3)

L,C = map(int,sys.stdin.readline().split())
arr = list(map(str,sys.stdin.readline().split()))
arr.sort()
vowels = ['a','e','i','o','u']  # 모음
check = []  # 출력

def Permutation(idx,pointer):
    if len(check)==L:   # 재귀 반환조건 : 출력 개수
        c = 0   # 모음 개수
        for i in vowels:    # 모음, 자음 검사
            c += check.count(i)
        if c != 0 and L-c >= 2:
            print(''.join(check))        
        return
    if pointer >= C:    # 재귀 반환조건 : 집합 검사 개수
        return
    check.append(arr[pointer])
    Permutation(idx+1,pointer+1)    # 해당 문자열 채택
    check.pop()
    Permutation(idx,pointer+1)  # 해당 문자열 미채택

Permutation(0,0)

앞서 언급한 한 개의 모음만 검사하는 방법에 오류가 존재했다

L이 4이고 모음이 3개 있으면 자음은 1개가 되어 조건 성립이 안된다. 따라서 모음의 개수를 세어주고 L에서 빼준 값을 검사하여 자음의 개수도 함께 검사해주었다

 

시간복잡도는 O(2^C)가 될 것 같다