[Solved] BOJ: 1759 | 암호 만들기

문제

모음 최소 1개 이상, 자음 최소 2개 이상으로 총 l개의 단어 조합을 사전식으로 배열함

입력과 출력

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

---

문제 해결 요약

1. 입력 받은 단어들에서 자모음을 분리해 각각 자음리스트 모음리스트로 추가
2. 모음조합과 자음조합으로 단어 생성
3. 사전순 배열 및 출력

코드 설명

import 및 입력받기

-

from itertools import combinations
import sys
input = sys.stdin.readline

l, c = map(int, input().split())
letters = list(input().split())
answer = []
vows = ['a', 'e', 'i', 'o', 'u']

• 알파벳 종류 l과 단어 길이 c를 입력받음
• l개의 알파벳들을 입력받음

입력받은 알파벳들에서 자모음 분리

입력받은 알파벳들에서 자모음을 분리해서 각각 모음, 자음 리스트에 담는다.

-

letter_vow = []
letter_con = []

for letter in letters: # 자모음 분리
    if letter in vows:
        letter_vow.append(letter)
    else:
        letter_con.append(letter)

자모음 조합

combi 함수를 호출해 자모음 조합을 구한다

-

if l - len(letter_vow) >= 2:
    combis(len(letter_vow)+1)
else:
    combis(l-2+1)

• 단어의 길이에서 입력 받은 알파벳들에서의 모음의 개수를 뺀게 2보다 크거나 같다면
• 자음이 최소 2개 이상 되어야한다는 조건을 모음의 개수가 몇 개든지 항상 만족할 수 있다
• 그렇지 않다면
• 모음의 개수가 늘어남에 따라 자음이 최소 2개 이상 되어야하는 조건을 만족하지 못할 수 있으므로 자음의 최소개수(2개를)확보해서 계산해야한다.

단어 조합 함수

모음의 개수를 늘려가면서 모음 조합 + 자음 조합을 구한다

def combis(r):
    for i in range(1, r):
        for vow_combi in combinations(letter_vow, i):
            for con_combi in combinations(letter_con, l-i):
                tmp = list(vow_combi) + list(con_combi)
                tmp = sorted(tmp)
                answer.append(''.join(tmp))

• 파라미터로 모음의 최대 개수를 입력받는다
• 모음의 개수를 1부터 하나씩 늘려가면서
• 모음 리스트에서 모음 i개 조합을 구하고
• 자음 리스트에서 자음 (단어길이 - 모음 i개)개 조합을 구해서
• 단어를 완성한다

---

전체 코드

from itertools import combinations
import sys
input = sys.stdin.readline

l, c = map(int, input().split())
letters = list(input().split())
letter_vow = []
letter_con = []
answer = []
vows = ['a', 'e', 'i', 'o', 'u']

for letter in letters: # 자모음 분리
    if letter in vows:
        letter_vow.append(letter)
    else:
        letter_con.append(letter)

def combis(r):
    for i in range(1, r):
        for vow_combi in combinations(letter_vow, i):
            for con_combi in combinations(letter_con, l-i):
                tmp = list(vow_combi) + list(con_combi)
                tmp = sorted(tmp)
                answer.append(''.join(tmp))

if l - len(letter_vow) >= 2:
    combis(len(letter_vow)+1)
else:
    combis(l-2+1)

for a in sorted(answer):
    print(str(a))