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

오늘 풀어볼 문제는 암호 만들기이다.

문제

C개의 문자열 중에서 가능성 있는 암호를 모두 구해라

암호 조건

1. 서로다른 L개의 알파벳 소문자
2. 최소 한 개의 모음, 최소 두 개의 자음
3. 알파벳 오름차순

풀이 과정

그냥 암호로 가능한 모든 조합을 구한 다음에
그 조합이 조건에 맞는 지 판단해서 조건에 맞으면 출력하면 되는 거 아닌가? 해서 그렇게 풀어 봤다.

1. 가능한 모든 암호 조합을 구함 (주어진 알파벳 중에서 L개를 순서없이 중복없이 뽑음)
   (이 때 sort 후에 comb를 함으로써 결과가 암호 내부에서도, 각 암호끼리도 정렬되도록 함)
2. 각 조합들을 for문으로 돌면서 조건에 맞는 지 판별 후 맞으면 출력

from itertools import combinations

L, C = map(int, input().split())

alphabets = input().split()

# 길이가 L인 모든 조합, 증가하는 순서로 배열해야되기 때문에 sort 후 comb
alpha_combs = combinations(sorted(alphabets), L)

answer = []

for alpha_comb in alpha_combs:  # 가능한 조합 중에서
    consonant_count = 0
    vowel_count = 0

    # 자음 모음 개수 세기
    for alpha in alpha_comb:
        if alpha in "aeiou":
            consonant_count += 1
        else:
            vowel_count += 1

    # 모음이 1개 이상, 자음이 2 개 이상이면 출력
    if consonant_count >= 1 and vowel_count >= 2:
        print("".join(alpha_comb))

결과는 통과
골드 문제라길래 어려울 줄 알았는데 아니었다.

그리고 원래 재귀문제라고 하길래 재귀적으로도 풀어봤다.

전체 다 해보는데 조건에 맞지 않으면 빼면 되기 때문에 백트래킹 문제라고도 볼 수 있다.
그래서 아래와 같은 로직으로도 풀 수 있다.

1. 주이진 암호 길이가 되면 자음 모음 개수를 세서 조건에 만족하면 출력한다.
2. 주어진 암호 길이보다 작으면 현재 제일 끝에 있는 알파벳보다
   사전 순으로 더 큰 알파벳을 골라서 추가해서 dfs를 돌린다.
3. 1,2번을 계속 반복한다.

L, C = map(int, input().split())

alphabets = sorted(input().split())


def dfs(idx, codes):
    if L == idx:
        vowel_count = 0
        consonant_count = 0

        # 자음 모음 개수 세기
        for code in codes:
            if code in "aeiou":
                consonant_count += 1
            else:
                vowel_count += 1

        # 자음 2개 이상, 모음 한개 이상이면 암호가 될 수 있으므로 출력
        if consonant_count >= 1 and vowel_count >= 2:
            print("".join(codes))

    else:
        for i in range(idx, C):
            if codes and alphabets[i] <= codes[-1]:  # 오름차순 아니면 버림
                continue
            dfs(idx + 1, codes + [alphabets[i]])


dfs(0, [])