백준 - 2529번 부등호

코드

public class Main {

    static List<String> list = new ArrayList<>();
    static String next;
    static int n;
    static boolean[] used = new boolean[10];

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        sc.nextLine();
        next = sc.nextLine().trim().replace(" ", "");

        for (int i = 0; i <= 9; i++) {
            used[i] =true;
            dfs(String.valueOf(i));
            used[i]=false;
        }

        Collections.sort(list);

        System.out.println(list.get(list.size()-1));
        System.out.println(list.get(0));


    }

    static void dfs(String str) {
        int cur = str.length();
        int num = Character.getNumericValue(str.charAt(str.length() - 1));

        if (cur == n+1) {
            list.add(str);
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (used[i])
                continue;

            if ((next.charAt(cur - 1) == '<' && num < i) || (next.charAt(cur - 1) == '>' && num > i)) {
                used[i] = true;
                dfs(str + i);
                used[i] = false;
            }
        }
    }

풀이

🫡백트렉킹으로 풀 수 있는 문제이다. dfs를 탐색하면서 조건에 맞지 않는다면 가지치기를 통해 경우의 수를 줄이면 된다.

1. 첫 번째 for문은 시작지점이다. 0부터 9까지 수를 시작점으로 잡는다.
2. dfs탐색을 한다 이 때 이미 지나갔던 길이거나 부등호가 성립하지 않는다면 가지치기를 한다.
3. 사용해야 할 숫자를 다 사용했다면 조건에 만족하는 것으로 answer list에 넣는다.
4. 정렬을 통해 가장 가장 큰 숫자와 마지막 숫자를 가져온다.

출처 : 백준 - 2526번