백준 2529 : 부등호 [JAVA]

[문제 링크]

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

[난이도]

- Silver 1

 

[알고리즘]

- 백트래킹

 

[코드]

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

public class Main {
    static int k;
    static char[] operators;
    static boolean[] visited = new boolean[10];
    static List<String> results = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());

        // 공백을 없애고 각 글자를 char array로 담는다
        operators = br.readLine().replace(" ", "").toCharArray();

        solve("", 0);

        results.sort(String::compareTo); // results 리스트를 사전순으로 정렬

        System.out.println(results.get(results.size() - 1)); // 최댓값
        System.out.println(results.get(0)); // 최솟값
    }

    /**
     *
     * @param num 현재까지 생성된 숫자
     * @param index 현재 처리중인 숫자자리
     */
    static void solve(String num, int index) {
        if (index == k + 1) {
            results.add(num);
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (visited[i]) continue; // 이미사용한 숫자라면 통과

            // index가 0일경우에는 비교할 숫자가 하나밖에 없기때문에 다음숫자로 넘어감
            // 혹은 비교한 두 숫자가 주어진 부등호의 조건과 맞다면 계속 진행
            if (index == 0 || check(num.charAt(index - 1) - '0', i, operators[index - 1])) {
                visited[i] = true;
                solve(num + i, index + 1);
                visited[i] = false; // 완전탐색을 위해 복구
            }
        }
    }

    static boolean check(int a, int b, char operator) {
        if (operator == '<') return a < b;
        else return a > b;
    }
}

[풀이]

백트래킹 알고리즘을 활용할 때 넘겨주는 매개변수를 num : 현재까지 생성된 숫자, index 현재 처리중인 숫자 를 넘겨준다.

for문을 돌며 숫자 두개를 입력받은 부등호와 비교해 참일경우에만 다음숫자를 진행한다.