"중복 없이", "n개를 선택한다"라는 규칙을 통해 조합(combination)이 떠올랐다. C개의 문자들 중에서 L개의 문제를 골라서 암호를 만드는 경우의 수는 이라고 할 수 있다. 코드로는 itertools 모듈의 combinations 함수를 사용해서 모든 조합을 구할 수 있다.
combi = list(itertools.combinations(alpha, L))
조합을 꺼냈으면 해당 조합, 즉 암호가 우리가 원하는 조건에 만족하는지 확인해서 만족할 경우 출력한다.
if c in ["a", "e", "i", "o", "u"]:
consonant += 1
else:
vowel += 1
이처럼 문자 c가 모음에 속할 경우 consonant를 +1 해주고 그 외의 경우에는 vowel을 +1 해준다. 한 조합에 대해서 위 과정이 끝나면 모음과 자음 개수를 비교해서 조건에 만족할 경우 출력해준다.
조합(combination)을 이용한 코드를 작성한 후 오류 없이 결과 또한 정상적으로 출력되었다. 추가적으로 해당 문제를 백트래킹(back-tracking) 알고리즘으로도 해결할 수 있다고 해서 백트래킹 알고리즘에 대해 알아보았다.
해를 찾는 도중 해가 아니어서 막힐 경우, 되돌아가서 다시 해를 찾아가는 기법으로 최적화 문제와 결정 문제를 푸는 방법이 되기도 한다.
백트래킹의 구현은 대부분 BFS나 DFS와 함께 구현한다. 모든 경우의 수에서 한정 조건을 만족하는 경우를 탐색하는 것으로 어떤 노드의 유망성, 즉 해가 될만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전으로 돌아가(Backtracking)하여 다음 분기, 자식 노드로 간다. 해가 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning)한다고 한다.
따라서 이 문제에 백트래킹 알고리즘을 적용해서 풀려면 먼저 DFS 방식으로 모든 문자를 순차적으로 방문하는데 DFS 진행 깊이가 L이 된다면 더 이상의 진행을 멈추고 자음과 모음 개수를 판단하는 과정으로 바로 넘기면 된다.
1. 조합론
import sys
import itertools
input = sys.stdin.readline
L, C = map(int, input().split())
alpha = input().split()
alpha.sort()
combi = list(itertools.combinations(alpha, L))
ans = []
for s in combi:
consonant = 0
vowel = 0
for c in s:
if c in ["a", "e", "i", "o", "u"]:
consonant += 1
else:
vowel += 1
if consonant >= 1 and vowel >= 2:
for c in s:
print(c, end="")
print()
2.백트래킹
import sys
import itertools
input = sys.stdin.readline
L, C = map(int, input().split())
alpha = sorted(list(map(str, input().split())))
answer = []
def back_tracking(deep, idx):
if deep == L:
consonant = 0
vowel = 0
for c in answer:
if c in ["a", "e", "i", "o", "u"]:
consonant += 1
else:
vowel += 1
if consonant >= 1 and vowel >= 2:
print("".join(answer))
return
for i in range(idx, C):
answer.append(alpha[i])
back_tracking(deep + 1, i + 1)
answer.pop()
back_tracking(0, 0)