파이썬) 암호 만들기 - BOJ

https://www.acmicpc.net/problem/1759

from itertools import combinations
from collections import Counter
l, c = map(int, input().split())

arr = list(map(str, input().split()))
arr.sort()
result = []


for v in combinations(arr, l):
    # 조합을 짜줌
    c = Counter(v)
    # 조합 안 요소의 개수를 셈
    cnt = 0
    # 모음 수
    if 'a' in c:
        cnt += 1
    if 'e' in c:
        cnt += 1
    if 'i' in c:
        cnt += 1
    if 'o' in c:
        cnt += 1
    if 'u' in c:
        cnt += 1
        
    if l - cnt >= 2 and cnt >= 1:
        # 모음이 1개보다 많고, 암호문 길이에서 모음을 뺀 수(이 수는 자음수가 된다)가 1보다 크면 유효함 암호
        zz = [i for i in v]
        arr.sort()
        s = ''.join(zz)
        result.append(s)


for i in result:
    print(i)

 

이 문제의 조건을 보고 무조건 브루트 포스로 풀어야한다 생각했다.

우선 combinations로 조합을 짜 준뒤, 그 조합 안에서의 모음 개수를 살핀다.

그 뒤에 l-모음 개수 = 자음 개수 이므로 자음 개수 또한 조건문에 포함시킬 수 있다.

추가로 설명하자면 만약 조합 중 'aacci'라는 단어가 나올 경우 
if 'a' in c:
  cnt += 1
을 사용할 수가 없는데 위 코드가 성립하는 이유는 문제 조건 중 "중복된 알파벳은 없다."라는 항목 때문이다.

 

이 문제를 보고선 알고리즘 분류를 보았는데 백트래킹이 포함되어있었다.

이 문제를 백트레킹으로 어떻게 풀었을까?

 

다른 사람의 코드를 한 번 참조해봤따.

vowel = ['a', 'e', 'i', 'o', 'u']

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

words.sort() 

def check(arr):
    v_count, c_count = 0, 0 # 모음 개수, 자음 개수

    for i in arr:
        if i in vowel:
            v_count += 1
        else:
            c_count += 1

    if v_count >= 1 and c_count >= 2:
        return True
    else:
        return False

def backtracking(arr):

    if len(arr) == L:
        if check(arr):
            print("".join(arr))
            return

    for i in range(len(arr), C):
        if arr[-1] < words[i]:
            arr.append(words[i])
            backtracking(arr)
            arr.pop()

for i in range(C - L + 1):
    a = [words[i]]
    backtracking(a)

내가 작성한 코드와 로직은 별반 다른게 없긴하다.