[伯俊#1759]パスワードの作成


1.問題の説明



2.解説


問題は、入力可能なすべてのアルファベットからなる組合せを作成し、2つの補助音を含む1つの母音を検索して出力することです.Pythonのコンビネーションライブラリは利用できますが、今回はbacktrackingで直接コンビネーションを実現しました.
# nCr 조합을 백트래킹을 이용해 구하는 함수
def combinations(array, visited, start, n, r):
    if r == 0:
        for i in range(n):
            if visited[n]:
                print(n, end="")

        return
    
    for i in range(start, n):
        visited[i] = True
        combinations(array, visited, i + 1, n, r - 1)
        visited[i] = False
この関数を使用すると、n長の文字列からr文字を抽出し、作成可能なすべての文字列を出力できます.ここで2つ以上の子音と1つ以上の母音をチェックして終了です.

3.正解コード

from sys import stdin
input = stdin.readline


def solution(alpha_list, visited, start, n, r, moeum):
    if r == 0:
        res = ""
        m_cnt = 0  # 모음 개수
        j_cnt = 0  # 자음 개수
        for i in range(n):
            if visited[i]:
                if alpha_list[i] in moeum:
                    m_cnt += 1
                else:
                    j_cnt += 1
                res += alpha_list[i]

	# 자음 2개 모음 1개 이상인 문자열만 출력
        if m_cnt >= 1 and j_cnt >= 2:
            print(res)
        return 
    
    for i in range(start, n):
        visited[i] = True
        solution(alpha_list, visited, i + 1, n, r - 1, moeum)
        visited[i] = False


if __name__ == '__main__':
    L, C = map(int, input().split())
    alpha_list = list(input().rstrip().split(" "))
    moeum = set(["a", "e", "i", "o", "u"])
    alpha_list.sort()
    visited = [False] * C

    solution(alpha_list, visited, 0, C, L, moeum)