BOJ_2529 / 부등호

📌 문제 탐색하기

• 입력:
  • 첫 줄에 부등호 문자의 갯수를 나타내는 정수 k가 주어진다. k는 2이상 9 이하이다.
  • 두 번째 줄에는 k개의 부등호 기호가 하나의 공백을 두고 나열된다. 각 기호는 < 또는 > 이다.
• 출력:
  • 부등호 조건을 만족하는 k + 1 자리의 최대 정수와 최소 정수를 각각 첫 줄과 둘째 줄에 출력한다.

---

📌 어떤 알고리즘?

• DFS
  • 숫자 0부터 9까지 중 하나씩 선택하면서 조합을 만든다.
  • 각 자릿수를 하나씩 채우면서 다음 자릿수로 이동하는 과정에서 DFS가 사용된다.
• 백트래킹을 통한 가지치기
  • DFS는 ‘모든 경로’를 탐색하기에, 조건에 맞지 않는 경로는 버릴 필요가 있다.
  • 부등호 조건을 만족하지 않는 경우, 해당 경로를 더 이상 탐색하지 않고 이전 단계로 돌아가 다른 숫자를 시도하게 한다.
• DFS : 가능한 모든 조합을 하나씩 시도하면서, 깊이 있기 탐색하는 알고리즘이다.
• 백트래킹 : 조건을 만족하지 않는 경로는 빠르게 포기하고, 다른 경로로 돌아가는 방식이다. 이 문제에서는 부등호 조건을 통해 가지치기를 하고, visited 배열을 사용하면서 각 숫자가 중복되지 않도록 한다.

---

📌 코드 설계하기

• 입력 처리:
  • k와 주어진 부등호 들을 입력받아 크기가 k인 배열에 저장한다.
• 백트래킹으로 가능한 숫자 조합 찾기:
  • 가능한 숫자 조합을 찾고, 여기서 각 숫자마다의 방문여부를 체크하여 중복되지 않도록 한다.
  • depth가 k + 1이 되면 해당 문자열이 완성됨을 나타낸다. 나중에 각 문자열들을 정렬해서 최소 최대를 출력하면 된다.
  • 부등호 조건을 확인하고, 맞지 않으면 포기하고 다음 숫자를 탐색한다.
• 출력처리:
  • 문자열들이 포함된 컬렉션을 정렬해서 제일 앞에 있는 문자열과 제일 뒤에 있는 문자열을 출력한다.

---

📌 시도 회차 수정 사항

• 초기 구현:
  • 부등호 조건을 확인하는 부분에서 조건이 잘못 처리되어 결과가 잘못 출력하였다.
• 수정:
  • compare 함수에서 부등호 조건이 정확히 동작하도록 수정하였고, 백트래킹 시 방문 여부를 올바르게 설정하였다.

---

📌 정답 코드

package BOJ_2529;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_2529 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static String[] inEqualitySign;
    static int k;
    static boolean[] visited = new boolean[10];
    static List<String> results = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        k = Integer.parseInt(br.readLine());
        inEqualitySign = new String[k];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < k; i++) {
            inEqualitySign[i] = st.nextToken();
        }
        dfs("", 0);
        Collections.sort(results);
        System.out.println(results.get(results.size() - 1));
        System.out.println(results.get(0));
    }

    private static void dfs(String number, int depth) {
        if (depth == k + 1) {
            results.add(number);
            return;
        }
        for (int i = 0; i <= 9; i++) {
            if (!visited[i]) {
                if (depth == 0 || compare(number.charAt(depth - 1) - '0', i, inEqualitySign[depth - 1])) {
                    visited[i] = true;
                    dfs(number + i, depth + 1);
                    visited[i] = false;
                }
            }
        }
    }

    private static boolean compare(int n1, int n2, String sign) {
        if (sign.equals("<")) {
            return n1 < n2;
        } else {
            return n1 > n2;
        }
    }
}

---

📌 시간 복잡도?

• 시간 복잡도
  • DFS를 사용하여 가능한 모든 숫자 조합을 생성하므로, 시간 복잡도는 O(10!), 3,628,000번 에 가깝긴 하지만, 백트래킹으로 일부 경로를 가지치기하여 최적화를 수행한다.
  • 1초는 약 10^7번 정도의 연산이 가능하다.
• 공간 복잡도
  • 결과 리스트를 저장하는 공간을 사용하므로, 최악의 경우 최대 10!개의 조합을 저장할 수 있다.