문제

입력 출력 예시

해결 방법

itertools 라이브러리를 사용하여 나올 수 있는 모든 순열을(후보 비밀번호) 구하고, 각 순열마다 조건을 검사하는 방법은 최대 경우가 15P15까지 나오므로 2초안에 풀 수 없다. 즉 모든 후보 비밀번호를 구해 조건을 판별하는 방식이 아닌 처음부터 비밀번호를 조건에 맞게 만들어야 한다.

비밀번호 조건

• 비밀번호에 있는 알파벳은 사전순으로 오름차순이다.
• 비밀번호에는 최소 모음 1개 이상, 최소 자음 2개 이상으로 이루어져 있다.

따라서 가능한 모든 비밀번호를 구하기 위해 백트래킹 알고리즘을 사용하여 재귀적으로 비밀번호의 알파벳을 하나씩 더하는 방식을 사용한다.

구현

1. ‘비밀번호는 사전순으로 오름차순으로 이다’라는 조건을 만족하기 위해 입력받은 알파벳을 사전순 오름차순으로 정렬해준다.
2. 백트래킹 알고리즘을 사용하여 알파벳을 비밀번호에 하나씩 넣어준다. 이때 백트래킹 함수는 아래 3가지 매개변수를 가진다.
3. 현 알파벳 위치(오름차순으로 정렬된 문자열만 가능하므로 이전 알파벳은 비밀번호에 넣지 않기 위해)
4. 현재 비밀번호의 길이를 의미하는 depth
5. 현재까지 만든 비밀번호인 password
6. 비밀번호의 길이가 L이 되면 자음과 모음 개수를 확인해 준다.
7. 조건이 맞으면, 출력해 준다.

🚩플로우