악곱 == 악성곱슬

백트래킹

---

이 문제는 순열을 구하는 문제이다. 이는 백트래킹으로 다음과 같이 해결할 수 있다.

1. 오름차순으로 정렬한다.
2. 모음, 자음을 매 level마다 확인한다.
3. 카운트가 충족되지 않으면 출력하지 않는다.

이 문제를 완전 탐색으로 풀 수도 있지만, 백트래킹으로 분류한 이유는, 순회를 할 때, for i in range(start, c): 이 구문에 의해서 오름차순이 아닌 경우는 전부 프루닝을 하여 풀 수 있기 때문이다.

구현

---

import sys

def backtrack(answer, v_cnt, c_cnt, depth, l, c, visited, start):
    if depth == l:
        if v_cnt >= 1 and c_cnt >= 2:
            print(answer)
        return
    for i in range(start, c):
        if visited[i]:
            continue
        visited[i] = True
        if seq[i] in vowel:
            backtrack(answer + seq[i], v_cnt + 1, c_cnt, depth + 1, l, c, visited, i)
        else:
            backtrack(answer + seq[i], v_cnt, c_cnt + 1, depth + 1, l, c, visited, i)
        visited[i] = False

def solution(l, c):
    seq.sort()
    visited = [False] * c
    backtrack("", 0, 0, 0, l, c, visited, 0)

if __name__ == "__main__":
    L, C = map(int, sys.stdin.readline().rstrip().split())
    seq = list(map(str, sys.stdin.readline().rstrip().split()))
    vowel = {'a', 'e', 'i', 'o', 'u'}
    solution(L, C)