[백준 2529번] 부등호 [JAVA]

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

 

 

 

1. 입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

 

 

2. 출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

 

 

3.문제풀이

dfs을 통해서 탐색을 진행해야하는데 이때 최대값을 구하는 탐색과 최소값을 구하는 탐색을 구분합니다.

부등호를 기준으로 dfs를 통해 탐색을 하게 되고 count가 N에 도달하게 되면 탐색이 종료되게 되고 return을 하면서 지나온 숫자를 ArrayList에 저장해 줍니다.

 

이때 최대값을 구하는 dfs 연산시 가장 먼저 도달하는 경우가 최대값이 나오는 경우가 되도록 탐색을 진행할 때 큰 수 부터 탐색을 진행하고 최소값을 구하는 dfs_m 연산시 가장 먼저 도달하는 경우가 최소값이 되도록 탐색을 진행할 때 작은 수 부터 진행하는 것이 핵심입니다.

 

 

4.소스코드

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

public class Main {


    static int N;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static char[] arr;
    static boolean [] check;
    static boolean flag;
    static ArrayList<String> temp;



    public static void main(String[] args) throws IOException {
        int ans = 0;
        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arr = new char[N];
        check = new boolean[10];
        for(int i=0; i<N; i++){
            arr[i] = st.nextToken().charAt(0);
        }
        for(int i=9; i>=0; i--){
            flag = false;
            check = new boolean[10];
            check[i] = true;
            temp = new ArrayList<>();
            dfs(i,0);
            if(flag){
                for(int j=temp.size()-1; j>=0; j--){
                    System.out.print(temp.get(j));
                }
                break;
            }

            
        }
        System.out.println();
        for(int i=0; i<=9; i++){
            flag = false;
            check = new boolean[10];
            check[i] = true;
            temp = new ArrayList<>();
            dfs_m(i,0);
            if(flag){
                for(int j=temp.size()-1; j>=0; j--){
                    System.out.print(temp.get(j));
                }
                break;
            }
        }
    }
    static void dfs(int n, int count){
        if(count == N){
            flag = true;
            temp.add(String.valueOf(n));
            return;
        }
        if(arr[count] == '>'){
            for(int i = n-1; i>=0; i--){
                if(!check[i]){
                    check[i] = true;
                    dfs(i,count+1);
                    if(flag){
                        temp.add(String.valueOf(n));
                        return;
                    }
                    check[i] = false;
                }

            }
        }else{
            for(int i=9; i>n; i--){
                if(!check[i]){
                    check[i] = true;
                    dfs(i,count+1);
                    if(flag){
                        temp.add(String.valueOf(n));
                        return ;
                    }
                    check[i] = false;
                }
            }
        }
    }
    static void dfs_m(int n, int count){
        if(count == N){
            flag = true;
            temp.add(String.valueOf(n));
            return;
        }
        if(arr[count] == '>'){
            for(int i = 0; i<n; i++){
                if(!check[i]){
                    check[i] = true;
                    dfs_m(i,count+1);
                    if(flag){
                        temp.add(String.valueOf(n));
                        return ;
                    }
                    check[i] = false;
                }

            }
        }else{
            for(int i=n+1; i<=9; i++){
                if(!check[i]){
                    check[i] = true;
                    dfs_m(i,count+1);
                    if(flag){
                        temp.add(String.valueOf(n));
                        return ;
                    }
                    check[i] = false;
                }
            }
        }
    }




}