[JAVA] 부등호 (백준 2529 )

 

 

www.acmicpc.net/problem/2529

2529번: 부등호

부등호의 수가 3 개 이며 서로 다른 한 자리 숫자 는 4 개 라고 가정해보자.

 

숫자 0부터9 까지 숫자들 중에 4개를 선택해서 모든 경우의 수를 따져야 하는가??

 

그렇지 않다. 

 

가장 작은수와 가장 큰 수를 구하는 것이 목적이기 때문에 가장 작은 수와 가장 큰 수의 조합은 이미 정해져 있다.

 

12,3,4 와 2,3,4,5 를 선택했다고 가정했을 때, 가장 작은 수는 1,2,3,4 에서 나올것이다.

 

마찬가지로 가장 작은수는 이미 0,1,2,3 의 순열중의 하나의 수로 정해져 있다.

 

가장 큰수도 역시 9,8,7,6 의 순열의 조합으로 결정된다.

 

import java.util.*;

public class Main{

    static boolean[] visited;
    static char[] op;
    static int[] small;
    static int[] big;
    static boolean flag;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        op = new char[k];
        for(int i=0;i<k;i++) op[i] = sc.next().charAt(0);
        small = new int[k+1];
        big = new int[k+1];
        for(int i=0;i<=k;i++){
            small[i] = i;
            big[i] = 9-i;
        }
        visited = new boolean[k+1];
        flag = false;
        dfs(new int[k+1],small,0);
        visited = new boolean[k+1];
        flag = false;
        dfs(new int[k+1],big,0);

        for (int i : big) {
            System.out.printf("%d",i);
        }
        System.out.println();
        for (int i : small) {
            System.out.printf("%d",i);
        }
        System.out.println();

    }

    static void dfs(int[] result,int[] arr,int idx){
        if(idx == arr.length){
            if(check(result,op)){
                for(int i=0;i<arr.length;i++) arr[i] = result[i];
                flag = true;
            }
        }
        else{
            for(int i=0;i<arr.length&&flag==false;i++){
                if(visited[i]) continue;
                visited[i] = true;
                result[idx] = arr[i];
                dfs(result,arr,idx+1);
                visited[i] = false;
            }
        }
    }

    static boolean check(int[] arr,char[] op){
        int i =0;
        for (char c : op) {
            if(c=='<') {
                if (arr[i] >arr[i + 1]) return false;
            }else{
                if( arr[i] < arr[i+1]) return false;
            }
            i++;
        }
        return true;
    }


}