[백준] 암호 만들기

문제

https://www.acmicpc.net/problem/1759

TC

combination의 시간복잡도: n! / r! / (n - r)!

Idea

문제의 입력값들의 최대가 15이기 때문에 combinations를 사용할 수 있겠다고 생각했다.
조합으로 만들어진 문자열을 정렬한 후, 문제의 조건이었던 모음 개수 >= 1, 자음 개수 >= 2를 만족하는지 체크하기 위해 check 함수를 만들어서 풀었다.

code (Python)

from itertools import combinations

def check(word):
    v = 'aeiou'
    # 사용된 모음 개수
    vcnt = 0

    for w in word:
        if w in v:
            vcnt += 1
    # 사용된 모음이 1개 이상, 자음이 2개 이상이라면 true
    return vcnt >= 1 and len(word) - vcnt >= 2

# 입력 조건
l, c = map(int, input().split())
alpha = list(map(str, input().split()))

word = set()
for comb in combinations(alpha, l):
    temp = ''.join(sorted(comb))
    #최소 한 개의 모음과 최소 두 개의 자음으로 구성됐다면
    if check(temp):
        word.add(temp)

# 사전순 출력
for i in sorted(word):
    print(i)

self code review

combinations를 사용해서 풀었다. 다만 걸리는 것은, 시간복잡도가 크다는 것이다.
백트래킹으로도 한 번 다시 풀어보려고 한다.

추가

DFS로 풀어본 풀이를 추가하려고 한다.

def check(word):
    vowel = 'aeiou'
    v_cnt = 0

    for w in word:
        if w in vowel:
            v_cnt += 1

    if v_cnt >= 1 and len(word) - v_cnt >= 2:
        print("".join(word))

temp = []
def dfs(cnt, start):
    if cnt == l:
        check(temp)
        return

    for i in range(start, c):
        if not visited[i]:
            visited[i] = True
            temp.append(alpha[i])
            dfs(cnt+1, i+1)
            visited[i] = False
            temp.pop()

l, c = map(int, input().split())
alpha = sorted(list(map(str, input().split())))
visited = [False] * c

dfs(0, 0)