백준 1759 암호 만들기 파이썬

오 로직 짜면서 많이 어려웠는데 한방에 통과해서 기분 좋다ㅎ-ㅎ

 

핵심 : DFS

 

순열을 전체 만들면 무조건 시간초과가 날 것 같았고, 백트랙킹이 문제 분류에 있는걸 보면 조건으로 쳐내야한다는 것 같은데 순열을 만든다고 생각하니 막막했지만 그럴 필요는 없었던 것 같다.

내장함수 sort를 썼는데 지양해야하지만 이걸 해주지 않았더니 c 뒤에 t 검사를 안해서 일단 정렬을 했다.

ord()로 알파벳의 순서를 비교했다. 근데 sort를 해서 필요 없었나? 아니겠지? 일단 여기서 중복도 걸러졌다.

그리고 atw 처럼 4글자를 만들 수 없는 경우도 처리했다. 이땐 for문을 멈추는게 아니고 그냥 dfs 함수를 끝내버렸다.

 

L, C = map(int, input().split())
chars = list(input().split())
chars.sort()
vowels = ['a', 'e', 'i', 'o', 'u']
last_index = C - L + 1
starts = chars[:last_index]


def dfs(string, vowel, consonant):
    # 기저조건
    if len(string) == L:
        if vowel > 0 and consonant > 1 :
            print(string)
        return

    # 다음 문자를 추가할지 말지 결정하기
    now = string[-1]
    for index in range(vowel+consonant,C):
        next = chars[index]
        # 1. 알파벳 순서를 확인한다.
        if ord(now) >= ord(next):
            continue
        # 2. 얘부터 4문자를 만들 수 없으면 끝내버려
        if len(string)+len(chars[index:]) < L:
            return
        # 다음 문자 추가하기
        if next in vowels:
            dfs(string+next, vowel+1, consonant)
        else:
            dfs(string+next, vowel, consonant+1)


for start in starts:
    if start in vowels:
        dfs(start, 1, 0)
    else:
        dfs(start, 0, 1)

노트에 필기하다가 어려워서 못 만들고 있었는데 외려 코드로 짜다보니 수월하게 풀렸다?!