[백준] 2529번: 부등호 (JAVA, 문제, 문제풀이)

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

2529번: 부등호

 

순열을 통해서 모든 경우의 수를 구하고 부등호 비교를 해서 올바른 값 중 최대값과 최소값을 뽑는 문제.

 

푸는 방식이 배우고 싶은 아이디어라서 글로 남긴다.

 

첫 번째 실패 코드 (시간 초과): 부등호를 경우의 수마다 매번 확인하고, 최대값 최소값도 계산

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{
    public static int[] bucket;
    public static int k;
    public static String[] sign;
    public static String max = "";
    public static String min = "";
    public static boolean[] check = new boolean[10];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        sign = br.readLine().split(" ");
        bucket = new int[k+1];

        for (int i = 0; i <= k; i++) {
            max = max + "0";
            min = min + "9";
        }

        DFS(0);

        System.out.println(max);
        System.out.println(min);
    }

    public static void DFS(int depth) {
        if (depth == k+1) {
            String temp = Arrays.toString(bucket).replaceAll("[^0-9]","");;
            int prev = bucket[0];
            for (int i = 1; i <= k; i++) {
                if (sign[i-1].equals(">") && prev > bucket[i]) {
                    prev = bucket[i];
                } else if (sign[i-1].equals("<") && prev < bucket[i]) {
                    prev = bucket[i];
                } else {
                    return;
                }
            }

            boolean maxFlag = true;
            boolean minFlag = true;

            for (int i = 0; i <= k; i++) {
                if (maxFlag && bucket[i] > Integer.parseInt(String.valueOf(max.charAt(i)))) {
                    max = temp;
                    maxFlag = false;
                } else if (maxFlag && bucket[i] > Integer.parseInt(String.valueOf(max.charAt(i)))) {
                    maxFlag = false;
                }

                if (minFlag && bucket[i] < Integer.parseInt(String.valueOf(min.charAt(i)))) {
                    min = temp;
                    minFlag = false;
                } else if (minFlag && bucket[i] > Integer.parseInt(String.valueOf(min.charAt(i)))) {
                    minFlag = false;
                }

                if (!maxFlag && !minFlag) {
                    break;
                }
            }
            return;
        }

        for (int i = 0; i < 10; i++) {
            if (!check[i]) {
                bucket[depth] = i;
                check[i] = true;
                DFS(depth + 1);
                check[i] = false;
            }
        }
    }
}

 

 

두 번째 실패 코드 (시간 초과): 부등호를 경우의 수마다 매번 확인하고, 최대값 최소값은 어차피 순열의 끝과 처음이므로 생략

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{
    public static int[] bucket;
    public static int k;
    public static String[] sign;
    public static String max = "";
    public static String min = "";
    public static boolean[] check = new boolean[10];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        sign = br.readLine().split(" ");
        bucket = new int[k+1];

        DFS(0);

        System.out.println(max);
        System.out.println(min);
    }

    public static void DFS(int depth) {
        if (depth == k+1) {
            String temp = Arrays.toString(bucket).replaceAll("[^0-9]","");;
            int prev = bucket[0];
            for (int i = 1; i <= k; i++) {
                if (sign[i-1].equals(">") && prev > bucket[i]) {
                    prev = bucket[i];
                } else if (sign[i-1].equals("<") && prev < bucket[i]) {
                    prev = bucket[i];
                } else {
                    return;
                }
            }

            if (min.isEmpty()) {
                min = temp;
            }
            max = temp;
            return;
        }

        for (int i = 0; i < 10; i++) {
            if (!check[i]) {
                bucket[depth] = i;
                check[i] = true;
                DFS(depth + 1);
                check[i] = false;
            }
        }
    }
}

 

 

세 번째 성공 코드: 이미 정해진 순열에 대해서는 부등호 비교가 미리 되고 변한 부분에 대해서만 부등호 비교 진행

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{
    public static int[] bucket;
    public static int k;
    public static String[] sign;
    public static String max = "";
    public static String min = "";
    public static boolean[] check = new boolean[10];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        sign = br.readLine().split(" ");
        bucket = new int[k+1];

        DFS(0);

        System.out.println(max);
        System.out.println(min);
    }

    public static void DFS(int depth) {
        if (depth == k+1) {
            String temp = Arrays.toString(bucket).replaceAll("[^0-9]","");;

            if (min.isEmpty()) { // 부등호 조건을 만족하는 첫 번째 순열
                min = temp;
            }
            max = temp; // 부등호 조건을 만족하는 마지막 나온 순열

            return;
        }

        for (int i = 0; i < 10; i++) {
            if (depth > 0) {
                if (!check[i] && compare(sign[depth-1], bucket[depth-1], i)) {
                    bucket[depth] = i;
                    check[i] = true;
                    DFS(depth + 1);
                    check[i] = false;
                }
            } else {
                if (!check[i]) {
                    bucket[depth] = i;
                    check[i] = true;
                    DFS(depth + 1);
                    check[i] = false;
                }
            }
        }
    }

    public static boolean compare(String sign, int prev, int now) { // 부등호 비교
        if (sign.equals(">") && prev > now) {
            return true;
        } else return sign.equals("<") && prev < now;
    }
}

 

찾아보니 이것 보다도 더 빠른 방법들도 있었다.

Ex) 투 포인트로 하는 방법