[BOJ] 1759. 암호 만들기

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

1759번: 암호 만들기

 

 

1. 해결방법

"""
1. 아이디어
- 최소 1개 이상의 모음(a e i o u)과 최소 2개 이상의 자음으로 구성되어 있고, 오름차순으로 정렬을 한다.
- if문으로 먼저 1개 이상의 모음을 구하고, 그 다음은 자음 2개 이상을 조건화 한다.
- 원소 중복이 일어나면 안되기 때문에 방문기록을 체크할 것이다.

2. 시간복잡도

3. 자료구조
- 백트래킹 : 재귀
"""

 

 

2. 정답코드

입력 예제(1)

4 6
a t c i s w

출력 예제(1)

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

 

코드

# input
L, C = map(int, input().split())
pwd = sorted(list(map(str, input().split())))

chk = [False for _ in range(C)]
answer = []
cnt1 = 0
cnt2 = 0


# recur
def recur(depth, idx):
    global cnt1, cnt2

    # 재귀 종료 지점
    if depth == L:
        cnt1 = 0
        cnt2 = 0

        # 현재 append된 answer 리스트르 for문으로 돌면서 모음 그리고 자음의 카운트를 +1씩 해준다.
        for i in range(L):
            if answer[i] in ['a', 'e', 'i', 'o', 'u']:
                cnt1 += 1
            else:
                cnt2 += 1
        # 모음 1개, 자음 2개 이상일 경우 출력, print
        if cnt1 >= 1 and cnt2 >= 2:
            print(''.join(map(str, answer)))
        return


    # 재귀
    for i in range(idx, C):
        if chk[i] == False:
            answer.append(pwd[i])
            chk[i] = True
            recur(depth + 1, i + 1)
            answer.pop()
            chk[i] = False


# mian
recur(0, 0)

import sys
from itertools import permutations, combinations

input = sys.stdin.readline

L, C = map(int, input().split())
chars = sorted(list(map(str, input().split())))
chk = [False] * C

char_list = []
for perm in combinations(chars, L):
    a, b = 0, 0
    for c in perm:
        if c in ['a', 'e', 'i', 'o', 'u']:
            a += 1
        else:
            b += 1
    if a >= 1 and b >= 2:
        print(''.join(map(str, perm)))