[백준] 부등호 (자바)

부등호

문제풀이

이 문제는 완전 탐색을 통해서 해당 조건에 일치하는 배열을 모두 만들어 그 중에서 최대값과 최소값을 찾는 문제다.

dfs 메서드로 재귀 방식을 이용하여 완전탐색을 진행한다.
dfs 메서드의 매개변수로는 저장할 문자열 str, 부등호 배열 ineqArr, 그리고 언제까지 재귀를 반복할지 정하는 depth로 설정한다.

dfs 메서드에서 반복문을 설정한 뒤
depth가 0인 경우에는 dfs(str+i, ineqArr, depth+1)을 실행하도록 하고

depth가 1이상일 때는 부등호의 방향이 어떤지에 따라 조건문을 설정해줘서 depth가 0일 때와 마찬가지로 dfs(str+i, ineqArr, depth+1)을 실행한다.
여기서, 조건문의 조건은 만약 부등호의 방향이 < 일때는 str의 마지막 문자str.charAt(str.length()-1)가 들어오는 숫자에 비해 (char) (i+'0')이 커야 하고 부등호의 방향이 > 일때는 반대가 되어야 한다.

위 풀이를 코드로 구현하면 아래와 같다.

구현코드

import java.awt.print.Pageable;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

import java.lang.*;

// baekjoon_10162

public class Main{

    static int num;
    static boolean[] visit = new boolean[10];

    static ArrayList<String> arrayList = new ArrayList<>();

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

        num = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        String[] ineqArr = new String[num];

        for(int i = 0 ;i<num; i++){
            ineqArr[i] = st.nextToken();
        }

        int[] numArr = new int[10];

        for(int i =0; i<10; i++){
            numArr[i] = i;
        }

        String str ="";
        // 완전탐색을 위한 dfs 메서드 실행
        dfs(str, ineqArr,0);

        // 생성된 경우들을 쭉 정렬하기
        Collections.sort(arrayList);

        // 가장 큰 수 출력
        System.out.println(arrayList.get(arrayList.size()-1));
        // 가장 작은 수 출력
        System.out.println(arrayList.get(0));

        bw.flush();
        br.close();
        bw.close();
    }

    public static void dfs(String str, String[] ineqArr, int depth){

        if (depth == num+1){
            arrayList.add(str);
            return;
        }

        for (int i = 0; i<10; i++){
            // depth가 0인 경우
            if (depth==0){
                visit[i] = true;
                dfs(str+i, ineqArr, depth+1);
                visit[i] = false;
            }

            // depth가 1이상일 때
            else if(ineqArr[depth-1].equals("<")){
                if (visit[i] == false && (str.charAt(str.length()-1) < (char) (i + '0'))){
                    visit[i] = true;
                    dfs(str+i, ineqArr, depth+1);
                    visit[i] =false;
                }
            }
            else if(ineqArr[depth-1].equals(">")){
                if (visit[i] == false  && (str.charAt(str.length()-1) > (char) (i + '0'))){
                    visit[i] = true;
                    dfs(str+i, ineqArr, depth+1);
                    visit[i] =false;

                }
            }

        }

    }

}

구현된 코드를 보니까 반복되는 부분이 최소화되도록 조건문을 수정할 필요가 있지 않을까 싶다.