[백준 1759] 암호만들기 - python

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

1759번: 암호 만들기

---

문제설명

주어진 알파벳 배열을 통해 L 길이의 암호를 오름차순으로 만들어라.

 조건 1. 암호는 반드시 오름차순이어야 한다.

 조건 2. 암호는 세글자 이상이며, 1개 이상의 모음과 2개 이상의 자음을 포함한다.

 

직관적인 접근 - 완전탐색

L 길이를 가지는 모든 경우의 수를 구하고, 경우의 수가 조건 1,2를 만족하는지 확인한다.

 

문제점 - 시간초과

모든 경우의 수를 탐색하여 비효율적

 

문제해결 - 백트래킹

탐색을 깊이 들어가기 전에 만들어지는 문자열이 오름차순인지 확인하여 오름차순이 아니면 더 들어가지 않는다.(가지치기)

또한 오름차순인 경우만 구하는 것을 이용하여 입력데이터의 범위를 줄인다. 예를 들어 C개의 알파벳으로 L 길이의 비밀번호를 오름차순으로 만들경우 각 자리수 i에 들어갈 수 있는 범위는 C-L+1 개이다. 따라서 모든 데이터를 다 넣어보는게 아니라 자리수 i 부터 C-L+i+1 개의 데이터로 제한한다.

 

소스코드

# 비밀번호에 모음 1개, 자음 2개인지 확인하기 위한 모음배열
vowel = ['a','e','u','i','o']
 
answer = []
 
# 비밀번호 길이 L과 후보알파벳 갯수 C를 입력받음
L ,C = map(int, input().split())
 
# 후보알파벳 문자를 배열로 입력받음
arr = list(map(str, input().split()))
 
# 정답을 오름차순으로 정렬해야 하기 때문에 후보 알파벳을 정렬해 놓는다.
arr.sort()
 
# 백트래킹 함수, idx = 비밀번호 입력 갯수, string = 만들고 있는 비밀번호 문자열
def find(idx, string):
    global L
    global answer
    global arr
    global last
 
    # 비밀번호를 다 만들었으면 비밀번호 조건에 해당하는지 확인하고 해당하면 정답배열에 push하고 리턴
    if idx == L:
        if checkCondition(string):
            print(string)
        return
    lastIdx = last+idx
    # 오름차순으로 정렬된 arr배열을 idx 번부터 끝까지 순회
    for x in arr[idx:lastIdx]:
        # 오름차순으로 만들기 위해 만들고 있는 비밀번호의 가장 끝자리보다 입력값이 큰지 확인한다.
        if string[-1] < x:
            string += x
            find(idx + 1, string)
            string = string[:-1]
    return
 
# 비밀번호 조건에 부합하는지 확인하는 함수
def checkCondition(string):
    global vowel
    isVowel = False
    isConsonant = 0
 
    for i,x in enumerate(string):
        if x in vowel:
            isVowel = True
        else:
            isConsonant += 1
 
    if isVowel and isConsonant > 1:
        return True
    return False
 
# 비밀번호를 만들때 사용할 문자열 변수
string = ''
last = C-L+1
# 첫 문자는 for문으로 입력하고 그 이후부터 find 내에서 추가한다.
for x in arr[:last]:
    string += x
    find(1,string)
    string = string[:-1]