[백준 1759번] 암호 만들기(Python)

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

난이도 : 골드 5

1759번: 암호 만들기

 

문제

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

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

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

입력

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

출력

 

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

 

 

---

📌 풀이 접근 방법

백준 N과 M(2) 문제와 유사한 유형! 

 

몇 가지 조건만 잘 따져주면 된다.

문제에 대놓고 "가능한" 암호를 모두 출력하라고 적혀있기 때문에 시간초과없이 모두 탐색해볼 수 있다면 완전 탐색에 대해서 고민해볼 수 있다.

 

L, C의 범위는 15 이하이기 때문에 모든 문자열의 종류에 대해서 포함할지의 여부를 따지는 이진트리 형태로 구성하게 된다면

최악의 경우 시간복잡도는 2^15이다.(즉, O(2^C)) 따라서 백트래킹으로 풀 수 있음!

 

백트래킹 유형대로 이 문제도 두 가지 뼈대로 구성할 수 있다.

 

1) 종료조건 

문자열의 인덱스가 C-1 보다 커질 때 

1-2 ) 정답 출력

문자열의 길이가 L이고, 문자열 내 모음의 개수가 1개 이상이고, 자음의 개수는 2개 이상일 때 정답 출력

2) 재귀 함수 호출

문자열을 포함하는 경우, 포함하지 않는 경우에 대해서 호출

 

 

이진트리 모양으로 그려보면,  다음과 같이 나타낼 수 있당

 

 

 

📌 나의 풀이

나는 모음 개수를 세주는 함수를 하나 만들어서 풀었다.

그리고 기존의 code 에서 모음개수를 빼면 

결국 자음밖에 남지 않기 때문에 2 이상이 되는 조건을 바로 검사할 수 있도록 했다!

L, C = map(int, input().split())
candidate = list(input().split())
candidate.sort()
ans = []

def count_vowel(code) :
    cnt = 0
    vowel = ['a', 'e', 'i', 'o', 'u']

    for i in code :
        if i in vowel :
            cnt += 1

    return cnt

def dfs(n, code) :
    # 종료조건  
    if n > C-1 :
        if (len(code) == L) and (count_vowel(code)) >= 1 and (L-count_vowel(code) >= 2): 
            print(code)
        return
    
    # 하부함수
    dfs(n+1, code + candidate[n])
    dfs(n+1, code)

dfs(0, '')

 

백트래킹 감 아주 조금 잡았어.. 🤓

 

 

✅ 오늘두 문제 풀이 인증