[백준] 2529번 : 부등호 - JAVA [자바]

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

dfs 알고리즘 문제이다.

0 부터 9 까지의 숫자를 K + 1 개 조합을 하는데 이때 부등호에 따라 올 수 있는 수가 달라진다.

종료 시점은 K + 1 개를 뽑았을 때 종료한다.

나머지는 코드의 주석을 보자.

public class Main {

    public static int K;
    // 제일 앞에 0이 올 수도 있으므로 String으로 처리했다.
    public static String MIN;
    public static String MAX;
    
    public static int[] answerArr;
    // 부등호 배열
    public static String[] letters;
    // 방문 여부 배열
    public static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        K = Integer.parseInt(br.readLine());

        letters = new String[K];
        visited = new boolean[10];
        answerArr = new int[K + 1];
        
        // 최대로 나올 수 있는 수는 10의 k+1 제곱보다 무조건 작다.
        MIN = String.valueOf((long) Math.pow(10, K + 1));
        MAX = String.valueOf(-1);

        String line = br.readLine();
        String[] split = line.split(" ");
        for (int i = 0; i < K; i++) {
            letters[i] = split[i];
        }

        dfs(0);

        bw.write(MAX + "\n");
        bw.write(MIN + "");

        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs(int depth) {
    	// 종료 시점 == K + 1개를 조합 다 했을 때
        if (depth == K + 1) {
        	// 뽑은 정수 조합을 String으로 변환한다.
            String str = "";
            for (int num : answerArr) {
                str += num;
            }
            // 변환한 String은 범위가 Integer를 넘을 수 있으므로 long으로 변환
            long num = Long.parseLong(str);
            // 최대값 최소값과 비교하여 업데이트 해준다.
            if (Long.parseLong(MAX) < num) {
                MAX = str;
            }
            if (Long.parseLong(MIN) > num) {
                MIN = str;
            }
            return;
        }
        // 각 자리 마다 0부터 9까지 넣을 수 있다.
        for (int i = 0; i < 10; i++) {
        	// 아직 뽑지 않은 수이다.
            if (!visited[i]) {
            	// 제일 처음에는 왼쪽에 부등호가 없기 때문에 모든 수가 올 수 있다.
                if (depth > 0) {
                	// depth 번째 수를 뽑을 때
                    // depth - 1 번째의 수에 대해
                    // 부등호를 본다.
                    // "<" 이면 depth 번째 수는 depth - 1 번째 수보다 커야 된다.
                    // i를 전에 뽑은 수 보다 큰 것들만 본다.
                    if (letters[depth - 1].equals("<")) {
                        if (answerArr[depth - 1] < i) {
                            visited[i] = true;
                            answerArr[depth] = i;
                            dfs(depth + 1);
                            visited[i] = false;
                        }
                    }
                    // 반대 조건 ">"
                    else {
                        if (answerArr[depth - 1] > i) {
                            visited[i] = true;
                            answerArr[depth] = i;
                            dfs(depth + 1);
                            visited[i] = false;
                        }
                    }
                } else {
                    visited[i] = true;
                    answerArr[depth] = i;
                    dfs(depth + 1);
                    visited[i] = false;
                }
            }
        }
    }
}