[Python/파이썬] 백준 1759번 암호 만들기

https://www.acmicpc.net/problem/1759

 

이 문제는 백트래킹과 조합 두 가지 방법으로 풀 수 있다.

코드(백트래킹)

l, c = map(int, input().split())
alphabets = sorted(list(input().split()))


def check_validation(str):
    vowels = {"a", "e", "i", "o", "u"}
    vowel_cnt = 0
    for i in range(len(str)):
        if str[i] in vowels:
            vowel_cnt += 1
    if vowel_cnt >= 1 and len(str)-vowel_cnt >= 2:
        return True
    else:
        return False


def bt(idx, str):
    if len(str) == l:
        if check_validation(str):
            print(str)
        return
    if idx == c:
        return
    # idx번째 문자 포함
    bt(idx+1, str+alphabets[idx])
    # idx번째 문자 포함 X
    bt(idx+1, str)


bt(0, "")

 

1. 입력받은 알파벳들을 `alphbets` 배열에 저장해둔다. 이때 이 배열을 사전순으로 정렬해두면 나중에 출력할 때 사전순을 신경쓰지 않아도 된다.

2. `bt()`

  2-1. `str`의 길이가 `l`이 되면 문제에서 주어진 암호의 조건을 만족하는지 확인(`check_validation()` 함수 이용)하여 만족한다면 출력한다.

  2-2. idx가 c가 되면, 즉 alphabets의 문자들을 모두 탐색했다면 return

  2-3. idx번째 알파벳을 포함하는 경우와 포함하지 않는 경우로 나누어서 재귀 호출한다.

코드(조합)

from itertools import combinations

l, c = map(int, input().split())
alphabets = set(input().split())

vowels = alphabets & {"a", "e", "i", "o", "u"}
constants = alphabets - {"a", "e", "i", "o", "u"}

answer = []
for vowel_num in range(1, min(len(vowels)+1, l-2+1)):
    constant_num = l-vowel_num
    for vowel_comb in combinations(vowels, vowel_num):
        for constant_comb in combinations(constants, constant_num):
            answer.append("".join(sorted(list(vowel_comb+constant_comb))))

print(*sorted(answer, sep="\n"))

 

1. 집합 연산을 이용하여 `alphabets`에서 분리한 모음과 자음을 각각 vowels와 constants 집합에 저장한다.

2. `vowel_num`을 1부터 가능한 최대 모음 개수(`min(len(vowels)+1, l-2+1)`)까지 반복한다. 이때 자음의 개수는 만들어야 하는 전체 문자열 길이(`l`)에서 모음 개수를 뺀 값 `l-vowel_num`이다.

  2-1. 모음에서 `vowel_cnt`개만큼 뽑은 조합 `vowel_comb`을 만든다.

  2-2. 각 `vowel_comb`에서 모음을 ` constant_comb`개 뽑은 모음 조합을 생성한 뒤, 각 모음 조합과 자음 조합을 합쳐서 하나의 문자열을 생성하여 answer에 추가한다.

3. answer을 사전순으로 출력한다.