[Algo Rhythm🕺💃] BOJ 1759 - 암호 만들기

💫문제 분석

암호가 구성되는 서로 다른 알파벳 소문자의 개수를 $l$, 암호로 사용했을 법한 문자의 개수를 $c\ (3 \le l \le c \le 15)$라고 하자. 암호를 이루기 위해서는 다음과 같은 두 조건을 만족해야 한다.

1. 최소한 한 개 이상의 모음(a, e, i, o, u)로 이루어져 있다.
2. 최소한 두 개 이상의 자음들로 이루어져 있다.
3. 암호를 이루는 알파벳들은 증가하는 순서로 배열되어 있다.

암호로 사용했을 법한 문자들을 하나의 vertex로 보자. 그렇다면 이 문제는 $c$개의 vertex들 중 앞서 언급한 조건들을 만족하여 $l$개의 vertex들을 선택하는 backtracking 문제로 이해할 수 있다.

 

🔥문제 풀이

먼저 암호로 사용했을 법한 문자들을 저장한 배열 $alphabets$을 오름차순으로 정렬한다. 왜냐하면 암호에서 알파벳들은 증가하는 순서로 배열되었기 때문이다.

다음으로 암호를 저장하는 배열 $cipher$을 완성한 뒤 출력하는 함수 $f$를 실행하는데 $f$는 다음과 같다.

 

✨복잡도 분석

암호가 구성되는 서로 다른 알파벳 소문자의 개수를 $l$, 암호로 사용했을 법한 문자의 개수를 $c\ (3 \le l \le c \le 15)$라고 할 때, 시간 복잡도와 공간 복잡도는 다음과 같다.

 

⏰시간 복잡도 : $O(c^l)$

• $alphabets$를 오름차순으로 정렬하는데 $O(clogc)$가 소요됨
• $cipher$를 완성하기 위해 $f$를 recursive case마다 $c - idx (1 \le idx \le c)$번 호출하는데 이를 $l$번 반복한다. 따라서 $O(c^l)$이 소요됨

🏠공간 복잡도 : $O(c)$

• $alphabets$을 저장하기 위해 $O(c)$가 소요됨
• $cipher$를 저장하기 위해 $O(c)$가 소요됨

 

🌈코드

 

🌏문제 출처

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기