[백준][Python] 암호 만들기

728x90

문제 요약

C개의 알파벳이 주어지고 L개의 문자로 암호가 구성됩니다.

암호는 다음과 같은 특징을 가집니다.

1. 알파벳이 증가하는 순서대로 배열된다.

2. 최소 1개의 모음을 가지고 있다.

3. 최소 2개의 자음을 가지고 있다.

이 때 가능한 모든 암호를 출력하는 것이 문제이다.

 

내가 문제 풀 때 생각했던 것

이런 구현 문제는 조건만 순서대로 지켜준다면 답이 나옵니다. 이 문제는 완전 탐색이라 복잡하게 느낄 수도 있지만 Python만의 방식이면 쉽게 풀 수 있다고 느꼈습니다.일단 알파벳을 조합해야하므로 combination을 써야겠다고 생각했고 증가하는 순으로 배열해야하기 때문에 sort도 생각했습니다. 또한 모음을 주의해서 신경써야하므로 따로 선언해놓고 문제를 푼다면 수월하게 풀 수 있다고 생각했습니다.

 

1차 풀이

from itertools import combinations

L,C = map(int,input().split())
vowel = set('aeiou')
alpha = input().split()
alpha.sort()
answer = list(combinations(alpha, L)) # 오름차순으로 중복없는 조합
for combi in answer:
    ans = set(combi) - vowel # 차집합 = 만들어진 단어에서 모음을 제거한 경우
    if len(ans) >= 2 and len(set(combi) & vowel) >=1 : # 최소 2개의 자음으로 구성되고 최소 1개의 모음으로 구성
        print(''.join(combi))

먼저 vowel으로 모음을 지정해줬습니다. set 자료형으로 나중에 비교하기 쉽게 해놓았습니다.

그리고 입력받은 알파벳을 미리 정렬해놔서 조합 시 자동으로 오름차순으로 될 수 있도록 설정했습니다.

 

그렇게 나온 리스트 중 set 자료형을 이용해서 차집합을 만들었습니다. ans는 만들어진 단어에서 모음을 제거한 경우이므로 자음만 존재하는 경우입니다.

ans가 최소 2개 이상이고 만들어진 단어에서 모음과 교집합이 1개 이상(= 최소 1개의 모음으로 구성됨)이면 출력하게끔 코딩했습니다.

 

 

이 문제는 combinations를 구현하려면 어려운 문제이지만 활용할 줄 안다면 꽤 쉬운 문제가 됩니다. 역시 python은 라이브러리 사용이 중요하다는걸 또 한 번 깨닫게 됩니다..