[Algo Rhythm🕺💃] BOJ 2529 - 부등호

💫문제 분석

두 종류의 부등호 기호 ‘<’와 ‘>’가 $k$개 나열된 순서열을 $A$라고 하자. 그리고 $A$의 $i$번째 순서에 있는 부등호를 $A[i]\ (1 \le i \le k)$, 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자가 들어갈 자리를 $a_i\ (i \in \{x\ |\ 1 \le x \le (k + 1), \ x \in N\})$라고 하자. 예를 들어, 아래와 같은 $A$에 대하여 $A[i]$들과 $a_i$들은 다음과 같다.

 

이때 $a_i$는 다음과 같은 네가지 조건이 있다.

1. $i \ne j$일 때, $a_i \ne a_j$
2. $a_i \in \{x\ |\ 0\le x \le 9, x \in N\}$
3. $A[i]$가 '>'이면, $a_i \gt a_{i + 1}$ 이다.
4. $A[i]$가 '<'이면, $a_i \lt a_{i + 1}$ 이다.

 

문제는 $\min(a_1a_2...a_{k+1})$와 $\max(a_1a_2...a_{k+1})$를 출력할 것을 요구하는데 이를 위해 가능한 모든 $a_1a_2...a_{k+1}$을 확인해야 한다. 따라서, 이 문제는 backtracking을 구현하는 문제로 이해할 수 있다.

 

🔥문제 풀이

$\min(a_1a_2...a_{k+1})$와 $\max(a_1a_2...a_{k+1})$을 구하는 함수를 $f(a_1a_2...a_{k+1}, depth)$라고 하자.

 

$f$는 다음과 같다. 이때 $i \ne j$일 때, $a_i \ne a_j$라는 조건을 만족하기 위해 방문 여부를 조회해야 한다.

 

$f(Xa_2...a_{k + 1}, 1)\ (X \in [0, 9])$를 실행한 뒤 $\min(a_1a_2...a_{k+1})$와 $\max(a_1a_2...a_{k+1})$를 출력한다.

 

✨복잡도 분석

순서열 $A$의 길이를 $k$, $a_i$가 될 수 있는 값들의 개수를 $m$이라고 할 때, 시간 복잡도와 공간 복잡도는 다음과 같다.

 

⏰시간 복잡도 : $O(m!)$

• 최악의 경우 즉, $A$를 구성하는 모든 부등호들이 같을 경우 $a_{i+1}$를 찾기 위해 재귀 함수를 $m - i$번를 실행하기 때문에 $O(m!)$가 소요됨

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

• $A$를 저장하기 위해 $O(k)$가 소요됨
• $a_i$의 방문여부를 저장하기 위해 $O(k)$가 소요됨

 

🌈코드

 

🌏문제 출처

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

2529번: 부등호