[BOJ/Python] 1759_암호 만들기

문제 출처:https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

4 6
a t c i s w

예제 출력 1

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

 

---

풀이

 

주어진 입력 C,L에 대하여 C개의 문자들 중 L개를 이용하여 문자열을 만드는 문제이다. 주어진 조건을 살펴보면 다음과 같다.

1. 최소 한 개의 모음을 포함해야 한다.
2. 최소 두 개의 자음을 포함해야 한다.
3. 암호를 이루는 알파벳은 오름차순으로 구성되어있다.
4. 주어지는 알파벳은 중복되는 것이 없다.

예를 들어, 주어진 입력 a,d,b,c 에서 3개의 문자를 골라 만들어진 (a,d,c)를 문자쌍이라고 하자.

주어진 조건을 생각하지 않는다면, (a,d,c) 문자쌍을 이용해서 만들 수 있는 경우는 adc, acd, dac, dca, cad, cda 총 6가지가 있다. (수학에서의 순열과 같다.)

하지만, 조건 3를 고려한다면, 위의 경우 만들 수 있는 경우는 acd 1가지밖에 없다.

즉, 주어진 입력에서 L개의 문자를 골라 문자쌍을 만들면, 그 문자들로 만들 수 있는 결과는 정해져 있는 것과 같다.

따라서 순서는 이미 정해져 있으니 고려하지 않고 문자쌍을 만드는 행위에만 집중한다. ( 수학에서의 조합과 같다.)

이렇게 만들어진 문자쌍들로 문자열을 만들고, 1번과 2번 조건을 만족하는 경우에만 출력하는 방법으로 문제를 해결하였다.

 

이를 이용하여 코드를 작성하여 설명해보자면 다음과 같다.

 

import sys
from itertools import combinations
 
vowel=['a','e','i','o','u']
 
l,c = map(int,sys.stdin.readline().split())
c_list = list(sys.stdin.readline().split())
c_list.sort()
 
 
for alphabet in combinations(c_list,l):
    password=""
    count_vowel = 0
    count_consonant = 0
    for i in alphabet:
        password+=i
        if i in vowel:
            count_vowel+=1
        else:
            count_consonant+=1
    if count_vowel>=1 and count_consonant>=2:
        print(password)

1. 일단 조합을 이용하기 위해 itertools 모듈에 있는 combinations 클래스를 import해주었다.
2. 문자들을 입력받아 c_list에 저장하였고, 조합을 이용하여 뽑아낸 알파벳의 구성이 오름차순이어야 하기때문에 c_list를 오름차순으로 정렬해주었다.
3. combinations(c_list,l)를 이용하여 c_list에 있는 문자들 중 l개를 골라내어 for문을 수행하였다.
4. 골라낸 문자쌍을 반복문을 수행하여 하나씩 살펴보며 모음이라면(vowel 리스트에 존재한다면) 모음의 개수를 1 증가시키고, 아니라면(자음이라면) 자음의 개수를 1 증가시킨다.
5. 만약 모음의 개수가 1개 이상이고, 자음의 개수가 2개 이상이라면, 문제에서 요구한 가능성이 있는 암호이기 때문에 만들어진 password를 출력한다.