📚 1759 - 암호 만들기

암호 만들기

이해

(1) backtracking을 사용해야하는 문제이다.
이유로는 a ->c -> i -> s (o), a -> i -> c -> s (x)
이와 같이 현재 방문한 알파벳이 이전 알파벳 보다 우선순위가 높으면 결과에 반영하면 안되는 걸 체크 해야한다.
또한, 너비 우선 탐색을 사용하면 안되는 이유이다.

(2) 문제에서 데이터가 크지 않기 때문에 itertools 라이브러리에서 가져온 combinations(조합)을 사용하면 된다.

➡️ 더 간단하고, 속도도 빠르다.

소스

(1) backtracking

import sys

read = sys.stdin.readline


def dfs(len, idx):
    if len == l:
        vo = 0
        co = 0
        for i in range(l):
            if result[i] in 'aeiou':
                vo += 1
            else:
                co += 1
        if vo >= 1 and co >= 2:
            print(''.join(result))
        return
    else:
        for i in range(idx, c):
            if not check[i]:
                result.append(arr[i])
                check[i] = True
                dfs(len + 1, i + 1)
                check[i] = False
                del result[-1]  # 배열 마지막 공간 제거


l, c = map(int, read().split())
check = [False] * c
result = []
arr = read().split()
arr.sort()
dfs(0, 0)

(2) itertools - combinations

from itertools import combinations
 
L, C = map(int,input().split())
alpha = sorted(input().split())
words = combinations(alpha, L)
 
for word in words:
    cnt_vow = 0
    for i in word:
        if i in "aeiou":
            cnt_vow += 1
 
    if cnt_vow >=1 and L - cnt_vow >=2:
        print(''.join(word))

풀고 나서 깨달은 점으로는, 데이터의 크기가 엄청나게 크지 않는 이상 라이브러리를 호출해서 풀자!