[BOJ] 2529번 - 부등호 (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족하는 수열을 구해야한다.
→ 이 수열을 구하기 위해 백트래킹 방식을 사용한다.

 

 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.
→ 백트래킹을 할 때 사용할 배열은 위와 같고 중복되지 않는 값들로 이뤄지도록 visited 배열을 사용한다.

 

이제 여기서 모든 부등호 관계를 만족하는 수열 중 가장 큰 값과 가장 작은 값을 구해야한다.

이때 주의할 점은 첫 자리가 0인 경우도 정수에 포함해야한다. 즉, 0123과 같이 출력해야한다.

 

나는 이를 쉽게 다루기 위해 문자열로 답을 구하기로 했다.

그러나 최솟값과 최댓값을 계속 비교해서 갱신하는 것은 비효율적이다.

왜냐하면 내가 구현한 백트래킹 방식으로 구한 수열은 기본적으로 작은 수부터 큰 수 순서대로 구할 수 있기 때문이다.

만약 {1, 2, 3}으로 수열을 구한다고 하면 아래와 같이 나올 것이다.

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

그러므로 조건을 만족하는 모든 값들을 구하면

• 0번 인덱스의 값은 최솟값
• 마지막 인덱스의 값은 최댓값

이 될 것이다.

---

🍀 풀이 🍀

package Baekjoon;

import java.io.*;
import java.util.ArrayList;

public class BrutueForce2529 {

    static String[] sign;
    static boolean[] visited;
    static ArrayList<String> answers;


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

        int k = Integer.parseInt(br.readLine());
        sign = br.readLine().strip().split(" ");

        visited = new boolean[10];
        answers = new ArrayList<>();

        dfs(0, k+1, new int[k+1]);

        bw.write(answers.get(answers.size()-1)+"\n");
        bw.write(answers.get(0));
        bw.flush();
        bw.close();
    }

    static void dfs(int count, int n, int[] result) {
        if(count == n) {
            if(isOk(result)) {
                String t = "";
                for(int i : result) {
                    t += i;
                }
                answers.add(t);
            }
            return;
        }

        for(int i = 0; i < 10; i++) {
            if(!visited[i]) {
                visited[i] = true;
                result[count] = i;
                dfs(count+1, n, result);
                visited[i] = false;
            }
        }
    }

    static boolean isOk(int[] result) {
        for(int i = 0; i < sign.length; i++) {
            if(sign[i].equals("<")) {
                if(result[i] > result[i+1]) {
                    return false;
                }
            }
            else {
                if(result[i] < result[i+1]) {
                    return false;
                }
            }
        }
        return true;
    }
}