[백준-골드5] 1759번 암호 만들기(백트래킹, 파이썬)

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

1759번: 암호 만들기

 

<복습 체크>

22/02/08
O

 

<내 코드>

- 우선 입력받은 alpha 리스트를 정렬해줘야한다. 암호가 사전순이기 때문에

- 또한 암호가 사전순이기 때문에 abc <-> bac 이건 불가능하다.

  --> 따라서 dfs에 start 파라미터를 이용해서 중복을 방지했다.

- 그리고 암호에 같은 문자는 없으므로 if alpha[i] not in stack: 조건을 넣어서 중복을 방지했다.

- dfs 함수의 종료조건은 stack이 암호의길이 L과 같아질때이다.

 --> 이때 문제 조건을 만족하기 위해서 stack에 있는 문자의 자음과 모음의 수를 카운트한다.

 --> 모음 1개 이상, 자음 2개 이상의 조건으 만족할 때 stack을 출력하고 return한다.

vowels = ['a', 'e', 'i', 'o', 'u'] #모음
L, C = map(int, input().split())
alpha = list(input().split())

alpha.sort() #사전순으로 순회하기 위해 정렬

stack = []
def dfs(start):
    if len(stack) == L:
        cnt_con = 0 #자음수 카운트
        cnt_v = 0 #모음수 카운트
        for i in range(L):
            if stack[i] in vowels:
                cnt_v+=1
            else:
                cnt_con +=1
        if cnt_v>= 1 and cnt_con >=2: #모음 1개이상, 자음 2개 이상이면 출력
            print(''.join(stack))
        return
    
    for i in range(start,C):
        if alpha[i] not in stack:
            stack.append(alpha[i])
            dfs(i+1)
            stack.pop()
            
dfs(0)

 

<combinations 이용 코드>

- 정말 킹받는다,, 백트래킹으로 열심히 풀어도, 조합이나 순열을 쓰면 훨씬 쉽다.

- 보통 코테에서는 라이브러리 제한 안하는데,,, 백트래킹 안쓰면 죽는 경우가 분명 있겠지,,, 아직까진 모르겠다.

from itertools import combinations

vowels = ['a', 'e', 'i', 'o', 'u'] #모음
L, C = map(int, input().split())
alpha = list(input().split())

alpha.sort() #사전순으로 순회하기 위해 정렬

result = list(combinations(alpha, L))
for r in result:
    cnt_v = 0
    cnt_c = 0
    
    for i in range(L):
        if r[i] in vowels:
            cnt_v +=1
        else:
            cnt_c+=1
        
    if cnt_v>=1 and cnt_c>=2:
        print(''.join(r))