[伯俊#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)
Reference
この問題について([伯俊#1759]パスワードの作成), 我々は、より多くの情報をここで見つけました https://velog.io/@tenykim1109/백준-1759-암호-만들기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol