BOJ #1759 암호 만들기

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 1759. 암호만들기

문제 풀이

처음엔 모음-자음 조건에 따라 배열을 분리하여 비밀번호를 생성하려 했으니 답이 없는 난이도로 포기했다. input 범위를 잘 보니 해봐야 주어진 알파벳은 15개이다. 그렇다면 bruteforce 방법을 사용하고 생성된 비밀번호에 대해 조건검사만 수행해서 출력하는 방법이 오히려 난이도가 낮은 경우였다.

python 코드

def solve(l, strs, sol):
    if len(sol) == l: # 요구 길이 만족 시
        check = [] # 체크리스트 생성
        for v in 'aeiou': # 각 모음에 대해
            check.append(sol.count(v)) # 생성된 비밀번호의 모음개수
        if sum(check) == 0 or sum(check) > l - 2:
            return # 자음 1개 이하이거나 모음이 없는 경우 제거
        else:
            print(''.join(sol)) # 조건 충족 시 충력
            return # 종료
    for i, s in enumerate(strs): # 각 요소에 대해
        sol.append(s) # 더하기
        solve(l, strs[i + 1:], sol) # 재귀함수 호출
        sol.pop() # backtracking


l, c = map(int, input().split())
c_list = list(input().split())
c_list.sort() # 사전 순서대로 정렬
solve(l, c_list, [])