[JAVA] 백준 2529번- 부등호

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

2529번: 부등호

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int k;
    static char[] signs;
    static boolean[] visit;
    static List<String> list = new ArrayList<>();

    public static boolean check(int prev, int next, char sign) { // 부등호 식에 맞는 숫자인지 확인 
        if(sign == '<'){
            if(prev>next) return false;
        }else{
            if(prev<next) return false;
        }
        return true;
    }

    public static void dfs(int cnt, String num) {
        if (cnt == k + 1) {
            list.add(num);
            return;
        }
        for (int i = 0; i < 10; i++) {
            if (visit[i]) continue;

            if(cnt == 0 || check(Character.getNumericValue(num.charAt(cnt-1)), i, signs[cnt-1])){
                visit[i] = true;
                dfs(cnt + 1, num+i);
                visit[i] = false;
            }

        }
    }

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

        k = Integer.parseInt(br.readLine()); // 부등호의 개수
        signs = new char[k]; // 부등호 배열
        visit = new boolean[10];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            signs[i] = st.nextToken().charAt(0);
        }

        dfs(0, "");

        System.out.println(list.get(list.size()-1));
        System.out.println(list.get(0));

    }
}

 

 

처음엔 cnt가 k+1이 되었을 때 숫자가 부등호에 맞는지 확인하는식으로 풀었다가, dfs호출할 때마다 확인하는 식으로 해서 호출 횟수를 줄이는 걸로 변경했다.