[백준] 1759번 : 암호만들기

1759번: 암호 만들기

1759번: 암호 만들기

📄 문제개요

• 암호의 후보의 단어가 주어졌을때, 암호를 만들 수 있는 모든 경우의 수를 구한다.
• 암호는 문자가 오름차순이어야한다. 동일한 문자는 올 수 없다.
• 모음의 개수는 1개이상, 자음의 개수는 2개 이상 이어야한다.

🤔 문제분석

• 완전탐색문제로, 가능한 모든 조합을 확인해보면서 문제를 해결 할 수 있다.
• 필자는 2가지의 사항으로 문제를 해결 하였다.
• DFS로 가능한 모든 경우의 수를 탐색해보기
• Python 내장 라이브러리 Combination 라이브러리를 사용하여 경우의 수 만들기

📝 의사코드

1. 가능한 모든 경우의 수를 모두 구한다.
2. 자음의 개수와 모음의 개수가 해당조건을 맞는지 확인한다.

💻 코드

1. DFS로 가능한 조건 모두 구하기

import sys
input = sys.stdin.readline
mo_list = set(['a', 'e', 'i', 'o', 'u'])

L, C = map(int, input().split())
words = list(map(str, input().split()))
words.sort()

def dfs(word, ja, mo):
    if len(word) >= L:
        if ja >= 2 and mo >= 1:
            return [word]
        
        return []
    
    result = []
    for w in words:
        if w not in word:
            if len(word) and word[-1] > w:
                continue
            
            word += w
            if w in mo_list:
                result += dfs(word, ja, mo + 1)
            else:
                result += dfs(word, ja + 1, mo)
            
            word = word[:len(word)-1]
    return result
            
ans = dfs('', 0, 0)
for word in ans:
    print(word)

1. Combination 모듈을 사용한 모든 경우의수 구하기

import sys
from itertools import combinations

input = sys.stdin.readline
mo_list = set(['a', 'e', 'i', 'o', 'u'])
L, C = map(int, input().split())
words = list(map(str, input().split()))
words.sort()

for w in combinations(words, L):
    mo_cnt = len(set(w) & mo_list)
    if mo_cnt >= 1 and len(w) - mo_cnt >= 2:
        print(''.join(w))

🎯 피드백 및 개선사항

• 완전탐색 문제의 경우, 필자가 풀었던 1번 사항과 2번사항을 모두 할 줄 알아야, 다양한 문제에 접근이 가능하다.

❓다른사람은 어떻게 풀었을까?

• 다른사람들 모두 위와 같은 내용으로 문제를 해결 하였다.