[백준/Python] 1759번(백트래킹, 브루트포스)_암호 만들기

📌문제 유형

수학, 브루트포스 알고리즘, 조합론, 백트래킹 (골드5)

 

📌문제

1759번: 암호 만들기

 

📌나의 문제풀이

from itertools import combinations

l,c = map(int,input().split())
alphabet = list(map(str,input().split()))

ans = []
vowel = []
cons = []
# 모음, 자음 리스트 나누기
for alpha in alphabet:
    if alpha in ['a','e','i','o','u']:
        vowel.append(alpha)
    else:
        cons.append(alpha)

# 모음 1개 선택
for v in vowel:
    tmp = []
    tmp.append(v)
    # 자음 2개 선택(combination 사용)
    new_cons = list(combinations(cons,2))
    for i in range(len(new_cons)):
        tmp_ = tmp + list(new_cons[i])
        # 선택 안된 것 중, combination 사용하여 l-3개 선택
        remain = list(set(alphabet) - set(tmp_))
        choose = list(combinations(remain, l-3))
        for j in range(len(choose)):
            # tmp__로 문자 선택 후, 문자 순으로 정렬
            tmp__ = tmp_ + list(choose[j])
            tmp__.sort()
            ans.append(''.join(tmp__))

ans = sorted(list(set(ans)))
for a in ans:
    print(a)

 

📌 다른사람의 문제풀이

- combination 활용

import sys
from itertools import combinations

def make_code():
    result = []
    for c in list(combinations(chars, l)):
        vowel_cnt = consonants_cnt = 0
        for char in c:
            if char in vowels:
                vowel_cnt += 1
            else:
                consonants_cnt += 1
        if vowel_cnt > 0 and consonants_cnt > 1:
            result.append(''.join(c))
    return result

l, c = map(int,sys.stdin.readline().split())
chars = sorted(sys.stdin.readline().split())

vowels = set(['a','e','i','o','u'])

for p in make_code():
    print(p)

- 백트래킹 활용

mport sys


def back_tracking(cnt, idx):

    # 암호를 만들었을 때
    if cnt == l:
        # 모음, 자음 체크
        vo, co = 0, 0

        for i in range(l):
            if answer[i] in consonant:
                vo += 1
            else:
                co += 1

        # 모음 1개 이상, 자음 2개 이상
        if vo >= 1 and co >= 2:
            print("".join(answer))

        return

    # 반복문을 통해 암호를 만든다.
    for i in range(idx, c):
        answer.append(words[i])
        back_tracking(cnt + 1, i + 1) # 백트래킹
        answer.pop()


l, c = map(int, sys.stdin.readline().split())
words = sorted(list(map(str, sys.stdin.readline().split())))
consonant = ['a', 'e', 'i', 'o', 'u']
answer = []
back_tracking(0, 0)

 

📌 리뷰 

- C가 최대 15개이므로 l의 개수만큼 combination 후, 검토해도 시간초과 안남