[Python][백준 1759] 암호 만들기

[백준 1759] 암호 만들기 Python 풀이

📌 문제 분석

• 주어진 알파벳으로 구성된 암호를 생성하는 문제입니다.
• 암호는 서로 다른 L개의 알파벳 소문자로 구성되어야 하며, 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음이 포함되어야 합니다.
• 생성된 암호는 사전식으로 정렬되어 출력되어야 합니다.

🚨 시행착오

• 처음에는 모든 가능한 조합을 생성하기 위해 itertools의 permutations를 사용하려고 했습니다.
• 그러나 이 방법은 중복된 조합을 생성하고, 조건을 체크하는 데 비효율적이라는 문제가 있었습니다.

처음 코드의 문제점

• itertools를 사용하여 모든 순열을 생성하면, 조건을 만족하지 않는 조합도 포함되어 결과가 비효율적이었습니다.
• 또한, 모음과 자음의 개수를 체크하는 로직이 복잡해져 가독성이 떨어졌습니다.

어떻게 고쳤나요?

• 백트래킹을 사용하여 조건을 만족하는 조합만을 생성하도록 개선했습니다.
• 암호의 길이가 L에 도달했을 때만 유효성을 체크하여 불필요한 계산을 줄였습니다.

💡 해결 방안

import sys

def is_valid(password):
    vowels = set('aeiou')
    vowel_count = sum(1 for char in password if char in vowels)
    consonant_count = len(password) - vowel_count
    return vowel_count >= 1 and consonant_count >= 2

def backtrack(start, password, L, C, characters, results):
    if len(password) == L:
        if is_valid(password):
            results.append(password)
        return

    for i in range(start, C):
        backtrack(i + 1, password + characters[i], L, C, characters, results)

N, M = map(int, sys.stdin.readline().rstrip().split())
characters = sorted(sys.stdin.readline().rstrip().split())
results = []

backtrack(0, '', N, M, characters, results)

for result in results:
    print(result)

🎯 이 문제의 핵심 포인트

1. 조건을 만족하는 조합 생성: 모음과 자음의 개수를 체크하여 유효한 조합만 생성.
2. 백트래킹 활용: 재귀적으로 조합을 생성하여 효율성을 높임.
3. 정렬된 출력: 사전식으로 정렬된 결과를 출력하기 위해 입력을 정렬.
4. 유효성 체크: 조합의 길이가 L에 도달했을 때만 유효성을 체크하여 불필요한 계산 방지.

📝 예제로 이해하기

예제 입력:
4 6
a t c i s w

예제 출력:
acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

• 입력된 알파벳을 조합하여 조건을 만족하는 암호를 생성합니다. 각 조합은 사전식으로 정렬되어 출력됩니다.

✨ 이번 문제를 통해 배운 점

1. 효율적인 조합 생성의 중요성: 조건을 만족하는 조합만 생성하는 것이 성능에 큰 영향을 미침.
2. 백트래킹의 활용: 문제 해결에 있어 백트래킹 기법이 매우 유용함을 깨달음.
3. 유효성 체크의 필요성: 조합의 유효성을 체크하는 로직이 문제 해결의 핵심임.

🔍 코드 설명

• is_valid 함수: 주어진 암호가 유효한지 확인합니다. 모음과 자음의 개수를 세어 조건을 만족하는지 체크합니다.
• backtrack 함수: 재귀적으로 조합을 생성하며, 유효한 조합을 결과 리스트에 추가합니다.
• 메인 부분: 입력을 받고, 정렬한 후 백트래킹을 통해 조합을 생성하고 결과를 출력합니다.

이 문제를 통해 조합 생성의 효율성을 높이는 방법과 백트래킹의 중요성을 다시 한번 느낄 수 있었습니다.