[백준 2529 : JAVA] 부등호 / 백트래킹

문제

---

 

 

 

풀이

---

N개의 수열에서 M개의 수열을 찾는 N과 M 문제와 비슷하다.

 

0~9의 고정된 수열이 있고, 주어진 부등호 조건을 만족하는 수열을 찾으면 된다.

DFS 탐색의 깊이(인덱스)가 주어진 부등호의 갯수+1을 만족한다면 해당 수열은 부등호 조건을 만족하는 수열이다.

조건에 만족하는 모든 수열을 list에 모두 저장한 후, 정렬한 다음 처음과 마지막 값을 출력한다.

 

 

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N;
    private static char[] arr = new char[10]; // 부등호는 최대 9개임
    private static boolean[] visited = new boolean[10]; // 0~9까지 check
    private static List<String> ans = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            arr[i] = st.nextToken().charAt(0);

        dfs("", 0);
        Collections.sort(ans);

        System.out.println(ans.get(ans.size() - 1));
        System.out.println(ans.get(0));
        br.close();
    }

    private static void dfs(String num, int idx) {
        if (idx == N + 1) {
            ans.add(num);
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (visited[i]) continue;
            if (idx == 0 || ck(Character.getNumericValue(num.charAt(idx - 1)), i, arr[idx - 1])) {
                visited[i] = true;
                dfs(num + i, idx + 1);
                visited[i] = false;
            }
        }
    }

    private static boolean ck(int a, int b, char c) {
        if (c == '<') {
            if (a > b) return false;
        } else if (c == '>') {
            if (a < b) return false;
        }
        return true;
    }
}