[알고리즘 문제] 백준2529 - 부등호

문제는 다음의 부등호 기호 앞뒤에 서로 다른 숫자들을 넣었을 때, 부등호 기호를 만족하는 숫자조합의 최소/최대값을 구하는 문제이다.

 

대충 어떻게 푸는지는 알았는데, 생각보다 시간이 오래 걸렸다.

 

부등호 기호사이에 들어가는 숫자는 0~9이다. 0123456789 ~ 9876543210사이에서 부등호 기호를 만족하는 최소/최대값을 구해야 한다. 우리가 찾는 값은 최소/최대 2개의 값이기 때문에 모두 검사할 필요가 없다.

 

최대값은 9876543210부터 값을 감소하면서 부등호 기호 조건을 만족하는 첫번째 값이 최대값이 된다.

최소값은 0123456789부터 값을 증가하면서 부등호 기호 조건을 만족하는 첫번쨰 값이 최소값이 된다.

 

부등호 사이에 들어가는 숫자들을 구하는 방법은 재귀함수를 사용하였다.  숫자들은 모두 한번씩밖에 사용하지 못하기 때문에 이 부분은 check[]배열로 검사하였고, 숫자들은 stack에 넣어서 관리하였다.

 

재귀함수의 기저조건은 아직 최소/최대값을 찾지 않았고 숫자의 길이가 부등호 기호 갯수+1 로 하였다. 이렇게 한 이유는, 부등호 앞 뒤로 숫자들이 존재하기 때문에 "< >"인 경우, "1<3>2" 이런 식으로 숫자의 길이와 부등호기호 갯수가 같으면 이제 숫자가 부등호 기호를 만족하는지 검사한다.

 

검사는 check함수를 사용하였고, 만약 부등호 기호가 하나라도 맞지 않으면 해당 숫자는 틀린숫자가 된다.

 

최소/최대 값을 나누기위해 check함수와 재귀함수의 첫번째 인자로 c라는 값을 넘겨주었는데 1일때는 최대값, 2일때는 최소값을 구하도록 하였다.

 

특이한 점은, 재귀함수의 for문의 종료조건인데, 먼저 부등호 기호가2개("< >")인 경우는 총 3개의 숫자가 필요한다. 이때 부등호 기호의 배열크기는 2가 된다.

최대값의 경우 9부터 시작하여 9,8,7의 숫자가 필요하고 이는 9-operator.length의 종료조건을 가진다.

마찬가지로 최소값의 경우도 0부터 시작하여 0,1,2가 필요하기 때문에 종료시점은 0+operator.length의 종료조건을 가진다.

 

import java.util.*;

public class Main {
    static String[] operators;
    static Stack<Integer> stack = new Stack<Integer>();
    static boolean[] check = new boolean[11];
    static boolean isMaxFind = false;
    static boolean isMinFind = false;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        operators = sc.nextLine().split(" ");

        recursive(1, 0); // max
        stack.clear();
        recursive(2, 0); // min
    }

    static public void recursive(int c, int count) {

        // c : 1 -> max를 찾는 경우
        // c : 2 -> min을 찾는 경우
        if (c == 1) {
            if (!isMaxFind && count >= operators.length + 1) {
                check(c);
                return;
            }
        } else {
            if (!isMinFind && count >= operators.length + 1) {
                check(c);
                return;
            }
        }

        if (c == 1) {
            for (int i = 9; i >= (9 - operators.length); i--) {
                if (!isMaxFind && !check[i]) {
                    stack.push(i);
                    check[i] = true;
                    recursive(c, count + 1);
                    check[i] = false;
                    stack.pop();
                }
            }
        } else {
            for (int i = 0; i <= (0 + operators.length); i++) {
                if (!isMinFind && !check[i]) {
                    stack.push(i);
                    check[i] = true;
                    recursive(c, count + 1);
                    check[i] = false;
                    stack.pop();
                }
            }
        }
    }

    static void check(int c) {
        int left, right;
        String operator;
        String s = "";

        boolean isSuccess = true;

        for (int i = 0; i < operators.length; i++) {

            operator = operators[i];
            left = Integer.parseInt(s.charAt(i) + "");
            right = Integer.parseInt(s.charAt(i + 1) + "");

            if ((operator.equals(">")) && (left < right)) {
                isSuccess = false;
                break;
            } else if ((operator.equals("<")) && (left > right)) {
                isSuccess = false;
                break;
            }
        }

        if (isSuccess) {
            if (c == 1) {
                isMaxFind = true;
            } else {
                isMinFind = true;
            }
            System.out.println(s);

        }
    }
}