[Python] 백준 / gold / 1759 : 암호 만들기

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

백트래킹 문제지만, 파이썬 itertools 모듈의 combinations 클래스를 사용하면 훨씬 쉽게 풀리는 문제다. 그래도 백트래킹 연습을 위해 2가지 방법으로 모두 풀어봤다.

근데 아무리 봐도 그냥 combinations 로 푸는게 낫다. 시간 효율도 약 2배 나은걸 확인할 수 있었다..

combinations 코드

import sys
from itertools import combinations
L, C = map(int, sys.stdin.readline().split())
alphabet = list(sys.stdin.readline().split())
alphabet.sort()
combis = list(combinations(alphabet, L))
a = ['a', 'e', 'i', 'o' ,'u']   # 모음

for comb in combis:
    jaEum = 0
    moEum = 0
    result = ''
    for c in comb:
        if c in a:
            moEum += 1
        else:
            jaEum += 1
        result += c
    if moEum >= 1 and jaEum >= 2:
        print(result)

백트래킹 코드

import sys
sys.setrecursionlimit(10**6)
L, C = map(int, sys.stdin.readline().split())
alphabet = list(sys.stdin.readline().split())
mo = ['a', 'e', 'i', 'o', 'u']  # 모음
alphabet.sort()


def check(word):
    moEum = 0
    jaEum = 0
    for w in word:
        if w in mo:
            moEum += 1
        else:
            jaEum += 1

    return moEum, jaEum


def dfs(idx, word):
    word += alphabet[idx]
    result = check(word)
    if len(word) == L:
        if result[0] >= 1 and result[1] >= 2:
            print(word)
        return

    for i in range(idx+1, C):
        dfs(i, word)


for x in range(C):
    dfs(x, "")