백준 - [Gold 5] 1759번 암호 만들기

문제링크: https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

---

문제 설명

- L: 암호 자릿 수

- C: 알파벳 개수

- C개 알파벳으로 L 자릿 수의 암호를 만들 수 있는 모든 경우의 수를 사전순으로 출력

- 조건 1: 최소 1개의 모음 (a, e, i, o, u)

- 조건 2: 최소 2개의 자음

- 조건 3: 오름차순

- 중복 x 모두 소문자

---

풀이

python 내장 라이브러리인 combination을 사용하여 해결하였습니다. 처음에는 permutation으로 생각하여 풀었는데 시간 초과가 떴습니다. 생각을 해보니 comb로 모든 perm을 구현 가능하고 이미 오름차순으로 정렬을 한 채로 combination함수를 돌려서 조건1과 2만 체크해주면 되는 문제였습니다.

# 조건 1: 최소 1개의 모음
# 조건 2: 최소 2개의 자음
# 조건 3: 오름차순 정렬
mo = {'a', 'e', 'i', 'o', 'u'}
def check(password):

    j = set(password) - mo
    m = set(password).intersection(mo)
    # 조건1, 2 체크
    if len(j) < 2 or len(m) < 1:
        return False
    else:
        return True


from sys import stdin
from itertools import combinations

stdin = open("input.txt", "r")

# L: 암호 자릿 수
# C: 알파벳 개수
L, C = map(int, stdin.readline().split())

alphabets = stdin.readline().split()
alphabets.sort()


comb = combinations(alphabets, L)

for password in comb:
    if check(password): print(''.join(password))

또 다른 방식으로는 dfs를 사용한 백트래킹으로도 풀 수 있습니다. 이번 문제에서는 더 간단한 방법이 있기 때문에 스킵하겠습니다~

 

코드: github.com/smothly/Algorithm_Solving/blob/master/boj-1759.py