[BOJ/python] 1759: 암호 만들기

문제

✔️ gold 5

문제 흐름

문제를 읽고 또 비슷한 생각에 빠졌다. 경우의 수? dp아니야? 했는데,
경우의 수를 구하는 게 아니라, 모든 케이스를 출력해야하는 점에서 백트래킹이 더 적합하겠다는 생각이 들었다.
또한 앞의 케이스를 이용해서 뒤 케이스를 구할 수 있지만, 단순 계산으로 가능한 게 아니기 때문도 있었다.

일단 문제의 조건은 이러하다.
주어진 C개의 문자 중 L개의 문자를 고르는데,
반드시 모음 1개, 자음 2개를 포함한다.
그럼 여기서 조건을 만족했다! 라고 하기 위해 체크해야될 것은 세가지가 된다.

1. L개의 문자를 골랐는가?
2. 모음 1개를 포함하는가?
3. 자음 2개를 포함하는가?

이 조건들을 순서대로 묶어 condition이라는 리스트로 만들었다.

함수 bt를 돌면서 주어진 문자들 apv을 순서대로 방문하며
만약 모음이라면 조건 1과 2를 1씩 빼고 진행,
자음이라면 조건 1과 3을 1씩 빼고 진행한다.
여기서 사전순으로 정렬되어있어야 하기 때문에 함수를 돌기 전 apv을 정렬해줘야한다!

그리고 함수 bt의 처음에 조건을 만족하는지 확인한다.
모든 문자를 고른 경우,
자음과 모음의 조건을 만족했다면 (모두 음수) 고른 문자들을 출력하고,
아니라면 문자들을 출력하지 않고 넘어가도록 한다.

사실 세 조건을 인자로 일일이 넣자니 변수명 짓기도 어려워져서 하나로 묶었는데,
보기 좀 더 어려운 것 같다.
다음엔 condition[0] 정도는 따로 빼도 괜찮을 것 같다..

코드

# 암호 만들기

import sys
input = sys.stdin.readline

# c개의 문자중에서 조건을 만족하는 l개를 뽑는 모든 경우 (정렬)
# 최소 모음 1개 자음 2개
# 3 ≤ L, C ≤ 15

lst = []

def bt(apv: list, condition: list):
    # condition = [선택해야하는 전체 문자 수, 선택해야하는 남은 모음 수, 선택해야하는 남은 자음 수]
    if condition[0] <= 0:
        if condition[1] <= 0 and condition[2] <= 0:
            print("".join(lst))
        return

    for i in range(len(apv)):
        lst.append(apv[i])
        if apv[i] in "aeiou":
            # print(f"{apv[i]} - {lst} - {condition} 모음")
            # print(f"    {[condition[0]-1, condition[1]-1, condition[2]}")
            bt(apv[i+1:], [condition[0]-1, condition[1]-1, condition[2]])
        else:
            # print(f"{apv[i]} - {lst} - {condition} 자음")
            # print(f"    {[condition[0]-1, condition[1], condition[2]-1]}")
            bt(apv[i+1:], [condition[0]-1, condition[1], condition[2]-1])
        lst.pop()


if __name__ == "__main__":
    l, c = map(int, input().split())
    apv = input().split()

    apv.sort()
    bt(apv, [l, 1, 2])