BOJ 1759 암호 만들기

LONGNEW·2021년 1월 25일
0

BOJ

목록 보기
103/333

https://www.acmicpc.net/problem/1759
시간 2초, 메모리 128MB
input :

  • L, C (3 ≤ L ≤ C ≤ 15)
  • 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

output :

  • 사전식으로 가능성 있는 암호를 모두 출력

조건 :

  • 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성
  • 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열

일단 입력 받은 알파벳들을 자음, 모음으로 분류 한다.

for item in alpha:
    if item in ('a', 'e', 'o', 'i', 'u'):
        a.append(item)
    else:
        b.append(item)

역시 in 이 이럴 때 편한 거 같다.

그리고 암호의 구성이 최소 모음 1개, 최소 자음 2개이다.
그렇기 때문에 모음의 개수가 1 이상이어야 하기 떄문에, 모음 리스트에서 컴비네이션을 구할 때는 1이상부터 해서 모음 리스트 길이 만큼 뽑아야 한다.

자음의 경우엔 최소 2개이기 때문에 암호의 길이 l 에 이미 뽑은 모음의 개수 i를 빼서 2보다 크거나 같아야 한다.

for i in range(1, len(a) + 1):
    for mouem in combinations(a, i):
        if l - i >= 2:
            for jauem in combinations(b, l - i):
                temp = mouem + jauem
                temp = sorted(temp)
                temp = "".join(temp)
                ret.add(temp)

그리고 ret는 set으로 만들어서 중복이 이뤄지지 않게 했다.
마지막에 ret를 정렬해서 출력해주자.

import sys
from itertools import combinations

l, c = map(int, sys.stdin.readline().split())
alpha = list(sys.stdin.readline().split())
a = []
b = []
ret = set()

for item in alpha:
    if item in ('a', 'e', 'o', 'i', 'u'):
        a.append(item)
    else:
        b.append(item)

for i in range(1, len(a) + 1):
    for mouem in combinations(a, i):
        if l - i >= 2:
            for jauem in combinations(b, l - i):
                temp = mouem + jauem
                temp = sorted(temp)
                temp = "".join(temp)
                ret.add(temp)
ret = sorted(ret)
for i in ret:
    print(i)

0개의 댓글