[Python]1759번, 암호 만들기, 조합과 집합 다루기

목차

 

문제

 

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 

 

702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 

 

최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 

 

또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 

 

암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 

 

즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 

 

이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. 

 

C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 

 

다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

 

출력

 

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

 

풀이

 

문제 자체는 크게 어렵지 않으나 파이썬에서 집합과 조합을 다루는 법에 대해 정리하려고 글을 쓴다.

 

조합의 경우, 역시 알고리즘 풀기 좋은 언어인 파이썬답게 자체 지원하는 라이브러리와 메서드가 있다.

from itertools import combinations

위 코드와 같이 가져와서 사용하면 되는데, 특정 개수 n(n>l)의 원소를 가진 리스트에서 l개를 뽑아

 

조합을 만들고 싶으면 아래와 같이 입력하면 끝이다.

combinations(letters, l)

결괏값을 출력해 확인하고 싶으면 아래와 같이 입력하면 된다.

print(list(combinations(letters, l)))

이렇게 하면 아래와 같은 리스트를 출력하며, 우리가 사용해야 할 조합의 종류가 나타난다.

[('a', 'c', 'i', 's'), ('a', 'c', 'i', 't'), ('a', 'c', 'i', 'w'), ('a', 'c', 's', 't'), ('a', 'c', 's', 'w'), ('a', 'c', 't', 'w'), ('a', 'i', 's', 't'), ('a', 'i', 's', 'w'), ('a', 'i', 't', 'w'), ('a', 's', 't', 'w'), ('c', 'i', 's', 't'), ('c', 'i', 's', 'w'), ('c', 'i', 't', 'w'), ('c', 's', 't', 'w'), ('i', 's', 't', 'w')]

그리고 두 집합 사이의 연산.

 

전에도 정리한 적이 있지만 너무 오랜만에 만나니 헷갈려서 정리한다.

 

예를 들어, 다음과 같은 두 개의 집합이 있다고 하자.

s1 = set([1, 2, 3])
s2 = set([3, 4, 5])

이런 경우 두 집합의 기본적인 연산은 아래와 같이 정의된다.

#합집합
union_result = s1.union(s2)
union_result = s1 | s2

#교집합
intersection_result = s1.intersection(s2)
intersection_result = s1 & s2

#차집합
difference_result = s1.difference(s2)
difference_result = s1 - s2

#대칭 차집합
symmetric_difference_result = s1.symmetric_difference(s2)
symmetric_difference_result = s1 ^ s2

#부분집합, 상위집합 확인
is_subset = s1.issubset(s2)  # True
is_superset = s2.issuperset(s1)  # True

이렇게 주어진 기능을 활용하면, 이 문제를 푸는 코드는 굉장히 짧아진다.

 

바로 결과를 보자.

 

Python

 

import sys
from itertools import combinations

l, c = map(int, sys.stdin.readline().rstrip().split())
letters = sys.stdin.readline().rstrip().split()
letters.sort()

tmp = set("aeiou")

for password in combinations(letters, l):
    if len(set(password) & tmp) >= 1 and len(set(password) - tmp) >= 2:
        print("".join(password))

입력을 받아 조합을 생성하고, 그 내부에서 tmp와의 합집합과 차집합의 개수를 이용해

 

문제의 조건을 맞춰주었다.

    if len(set(password) & tmp) >= 1 and len(set(password) - tmp) >= 2:

이 부분에 대해서만 조금 더 설명하자면, 두 집합의 합집합이 1보다 크다는 말은 모음이 하나 이상 포함되어 있다는 뜻이고,

 

두 집합의 차집합이 2보다 크다는 말은 자음이 두 개 이상 포함되어 있다는 뜻이 된다.