[BOJ 1759] : 암호 만들기

N과 M 2번 풀이를 참고해 완성할 수 있었습니다.

푸는 순서

1. 입력을 사전순으로 정렬합니다.

2. 백트래킹을 이용해 조합을 구현합니다.

3. 모음, 자음 수를 체크해 조건을 충족하는 경우에만 출력합니다.

L, C = map(int, input().split())
characters = list(input().split())
characters.sort()
password = []
visited = [0] * C


def backtrack(depth, start):
    if depth == L:
        consonant = 0
        vowel = 0
        for word in password:
            if word == "a" or word == "e" or word == "i" or word == "o" or word == "u":
                vowel += 1
            else:
                consonant += 1
        if consonant >= 2 and vowel >= 1:
            for word in password:
                print(word, end="")
            print()
        return

    for i in range(start, C):
        if visited[i] == False:
            visited[i] = True
            password.append(characters[i])
            backtrack(depth + 1, i + 1)
            visited[i] = False
            password.pop()


backtrack(0, 0)

한가지 팁이라면, 중복 방지를 위해 사용한 단어를 체크할 때(13번 라인) if i in visited 처럼 in 문법을 사용하면 시간 초과가 납니다.
따라서 만약 파이썬으로 백트래킹 문제를 풀 때는 인덱스를 활용해 곧바로 접근하도록 해야 합니다!