문제

링크

풀이

조합으로 푸는 방법과 백트래킹으로 푸는 방법 2가지가 있다.
조합으로 풀 경우

1. C개의 문자를 오름차순으로 정렬한다.

2. L개를 뽑아 만들 수 있는 조합의 경우를 만든다.

3. 각각의 경우에 최소 1개의 모음과 최소 2개의 자음으로 구성되어 있는지 확인한 후 맞다면 출력한다.

백트래킹으로 풀 경우에도 위 방법과 비슷하다. 하지만 2번에서 조합을 만들지 않고 깊이탐색(dfs)을 진행한다. depth는 L이고, L까지 탐색을 완료한 후 최소 1개의 모음과 최소 2개의 자음으로 구성되어 있는지 확인 후 맞다면 출력한다. 깊이탐색(dfs)을 진행할 때, 한바퀴 탐색을 완료한 경우 탐색하지 않도록 idx를 조정해야한다. (이렇게 하지않으면 순열처럼 탐색한다. 즉, 조합의 방식으로 깊이탐색(dfs)를 진행하도록 하는 것이다!)

코드

조합

import sys
from itertools import combinations

input = sys.stdin.readline
L, C = map(int, input().split())
alphabet = list(input().split())
alphabet.sort()


def check(string):
    count = 0
    for alpha in string:
        if alpha == 'a' or alpha == 'e' or alpha == 'i' or alpha == 'o' or alpha == 'u':
            count += 1
    return count


for case in combinations(alphabet, L):
    if check(case) >= 1 and (len(case) - check(case)) >= 2:
        print(''.join(case))

백트래킹

import sys

input = sys.stdin.readline
L, C = map(int, input().split())
alphabet = list(input().split())
alphabet.sort()
visited = [0] * C


def check(string):
    count = 0
    for alpha in string:
        if alpha == 'a' or alpha == 'e' or alpha == 'i' or alpha == 'o' or alpha == 'u':
            count += 1
    return count


def dfs(depth, string, idx):
    if depth == L:
        if check(string) >= 1 and (len(string) - check(string)) >= 2:
            print(''.join(string))
            return

    for i in range(C):
        if idx < i:
            if not visited[i]:
                visited[i] = 1
                string.append(alphabet[i])
                dfs(depth + 1, string, i)
                visited[i] = 0
                string.pop()


dfs(0, [], -1)