백준: 1759 암호 만들기

문제

1759번: 암호 만들기

 

문제 풀이

 이 문제는 특정 문자들이 주어질 때, 해당 문자의 조합을 구하고 각 조합들이 1개 이상의 모음과 2개 이상의 자음으로 구성되는 경우를 찾는 문제이다. 앞서 다룬 15650N과 M (2)에서 중복을 허용하지 않는 조합을 DFS와 itertools를 활용하여 구한 적이 있다. 해당 풀이를 이해하고 있다면 쉽게 풀 수 있는 문제이다.

 

 기존의 조합 문제와 다른 점이 있다면, 자음과 모음의 수를 판단하는 부분이 필요하다는 것이다.

• depth가 L이면, 즉 L개 만큼의 문자를 선택했다면 다음과 같은 조건을 판단하여야 한다.
  • 모음이 1개 이상인가?
  • 자음이 2개 이상인가?
  • 위의 조건을 모두 만족하는 경우는 정답이다.

 

코드

DFS를 사용한 풀이

from sys import stdin


def dfs(idx, depth):
    if depth == l:
        v = 0
        ret = ''
        for i in check:
            ret += char[i]
            if char[i] in vowels:
                v += 1
        if v >= 1 and l - v >= 2:
            cases.append(ret)
        return

    for i in range(idx, c):
        if i not in check:
            check[depth] = i
            dfs(i, depth + 1)
            check[depth] = -1


if __name__ == '__main__':
    cases = []
    l, c = map(int, stdin.readline().split())
    char = sorted(stdin.readline().split())
    vowels = ('a', 'e', 'i', 'o', 'u')
    check = [-1] * l
    dfs(0, 0)

    for case in cases:
        print(case)

 

itertools를 활용한 풀이

from itertools import combinations
L, C = map(int, input().split())
strings = sorted(list(map(str, input().split())))
vowels = ('a', 'e', 'i', 'o', 'u')

for cases in combinations(strings, L):
    cnt = 0
    for case in cases:
        if case in vowels:
           cnt += 1
    if 1 <= cnt <= L - 2:
        print(''.join(cases))