[BOJ/PYTHON] 1759. 암호 만들기

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

문제 요약

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

암호는 알파벳순 정렬됨

사용했을 법한 문자의 종류 C가지가 주어졌을 때, 가능성 있는 암호 모두 구하기

핵심 아이디어

일반적인 백트래킹에 암호가 ‘사용했을 법한지’ 체크 로직을 넣으면 된다.

암호는 증가하는 순서로 배열되기에 정렬을 하고 시작한다.

풀이

# gold5-1759. 암호 만들기 

import sys
input = sys.stdin.readline

l, c = map(int, input().split())
string = list(map(str, input().split()))
vowels = ["a", "e", "i", "o", "u"]
array = []

string.sort()

def check(answer):
    vowel_cnt = 0
    consonant_cnt = 0
    for x in answer:
        if x in vowels:
            vowel_cnt += 1
        else: 
            consonant_cnt += 1
    if vowel_cnt >= 1 and consonant_cnt >= 2:
        return True
    return False

def back(i):
    if len(array) == l:
        if check(array):
            print(*array, sep='')
            return
    for idx in range(i, c):
        if string[idx] not in array:
            array.append(string[idx])
            back(idx + 1)
            array.pop()

back(0)

Trouble Shooting

처음에 string을 정렬 안 해줬었고,

백트래킹 다음 재귀를 할 때 idx 기준으로 +1을 해줘야 하는데 i + 1을 해줘서 사전순이 아닌 전의 이전의 것도 array에 넣게 되는 상황이 일어났다.

실행 시간

메모리 31256KB, 시간 52ms (python3)