[백준 #1759] 암호 만들기

1. 문제 설명

2. 해설

입력받은 알파벳으로 만들 수 있는 조합을 모두 만들고, 거기서 자음 2개 모음 1개를 포함하는 경우를 찾아서 출력해주면 되는 문제. 파이썬의 combinations 라이브러리를 써도 되겠지만, 이번에는 백트래킹으로 조합을 직접 구현했다.

# 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)