이번 문제는 보자마자 itertools의 permutations를 사용해야겠다고 생각했다. 그러나 더 좋은 방법이 있을 것 같아 고민하였고 백트래킹 방식으로 풀어보기로 하였다. 우선 사전 순으로 출력해야되기 때문에 입력받은 문자들을 사전 순으로 정렬시키고, 함수 내에서 문자들을 순회하며 정답 저장 리스트에 문자를 추가한 후 재귀 호출하고, 다시 추가한 문자를 빼는 방식으로 하여 완전 탐색 하였다. 정답 저장 리스트의 길이가 l과 같고, 모음의 수가 1보다 크고 l-1보다 작을 경우에만 문자열로 붙여 출력하도록 하였다.

• l, c를 입력받는다.
• arr을 정렬된 리스트로 입력받는다.
• 정답 저장 리스트 pw를 선언한다.
• dfs함수를 cur을 인자로 갖도록 하여 선언한다.
  -> 만약 pw의 길이가 l과 같고, pw 내의 모음의 갯수가 0보다 크고 l-1보다 작을 경우, pw를 문자열로 붙여 출력한다.
  -> cur부터 c까지 반복하는 i에 대한 for문을 돌린다.
  --> pw에 arr[i]를 넣는다.
  --> dfs(arr[i])를 재귀호출한다.
  --> pw에서 arr[i]를 뺀다.
• dfs(0)을 호출한다.

Code

l, c=map(int, input().split())
arr=sorted(list(map(str, input().split())))
pw=[]
def dfs(cur):
    if len(pw)==l and 0<pw.count('a')+pw.count('e')+pw.count('i')+pw.count('o')+pw.count('u')<l-1:
        print(''.join(pw))
    for i in range(cur, c):
        pw.append(arr[i])
        dfs(i+1)
        pw.pop()
dfs(0)