암호 만들기 ( 1759 번 )

1759번: 암호 만들기

 

---

🧠 알고리즘

• 백트래킹 (Backtracking / DFS)

 

✔️ 동작 방식

문제 핵심 아이디어

• 주어진 문자 집합(c_list)에서 길이 l의 문자열을 만들되,
  • 최소 1개의 모음(a, e, i, o, u)과 최소 2개의 자음이 포함되어야 함.
• 순서대로 증가하는 조합만 선택하며, 중복 사용은 불가.

재귀 구조

 

• 현재 수열의 길이가 l이면 모음 개수와 자음 개수로 조건을 바로 확인한다.
• 조건을 만족하면 ''.join(now_lst) 형태로 문자열을 만들어 즉시 출력한다.
• 아직 길이가 l보다 작으면,정렬된 문자 리스트(c_list)에서 현재 위치(start) 이후의 문자만 선택하여 탐색한다.
• 선택한 문자를 now_lst에 추가한 뒤,
  • 모음이면 m_count + 1
  • 자음이면 z_count + 1 로 값을 갱신하여 재귀 호출한다.
• 하위 재귀가 끝나면 pop()을 수행하여 상태를 복원하고 다음 문자를 탐색한다.

 

최종 출력

• 가능한 모든 문자열을 now_lst리스트에 저장한 뒤, ''.join(now_lst)로 출력.

---

 

🧾 코드

import sys
# 필요한 파라미터
# 1) 현재 위치 ( 이후 위치 부터 탐색 위함 )
# 2) 현재 깊이
# 3) 모음 갯수
# 4) 자음 갯수
# 5) 문자 배열

def _dfs(start, depth, m_count, z_count, now_lst):
    if depth == l:
        if m_count >= 1 and z_count >= 2:
            print(''.join(now_lst))
        return

    for idx in range(start, c):
        now_ch = c_list[idx]
        now_lst.append(now_ch)

        if now_ch in m_set:
            _dfs(idx + 1, depth + 1, m_count + 1, z_count, now_lst)
        else:
            _dfs(idx + 1, depth + 1, m_count, z_count + 1, now_lst)

        now_lst.pop()


l, c = map(int, sys.stdin.readline().rstrip().split())
c_list = sorted(sys.stdin.readline().rstrip().split())
m_set = {'a', 'e', 'i', 'o', 'u'}

_dfs(0, 0, 0, 0, [])

---

 

⏱️ 시간 복잡도

_dfs(start, depth, m_count, z_count, now_lst) : 백트래킹,, c개 문자중 l개 고르는 조합 ( 지수형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 지수형 시간 복잡도 ( O((lc​)×l) )