[백준][2529번] 부등호

문제 URL

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

나의 풀이

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //부등호
    static char[] str;
    static int[] ans;
    static int[] max = new int[10];
    static int[] min = new int[10];
    static boolean[] dup = new boolean[10];

    public static void main(String args[]) throws IOException {
        int size = Integer.parseInt(br.readLine());
        StringTokenizer stk = new StringTokenizer(br.readLine());
        str = new char[size];
        ans = new int[size + 1];
        for (int i = 0; i < size; i++)
            str[i] = stk.nextToken().charAt(0);

        //초기화
        for(int i=0; i<min.length; i++)
            min[i] = 9;

        go(0, size+1);

        for(int i=0; i<max.length; i++)
            bw.write(max[i]+"");
        bw.newLine();
        for(int i=0; i<min.length; i++)
            bw.write(min[i]+"");
        bw.flush();
        bw.close();
    }

    public static void go(int idx, int size) {
        if (idx == size) {
            if(isMax(max, ans)){
                max = ans.clone();
            }
            if(isMin(min, ans)){
                min = ans.clone();
            }
            return;
        }

        for (int i = 0; i <= 9; i++) {
            //중복검사
            if (dup[i])
                continue;
            //부등호에 따라 가능한 자리인지 검사
            if (!isCorrect(str,ans,idx, i))
                continue;
            dup[i] = true;
            ans[idx] = i;
            go(idx + 1, size);
            ans[idx] = -1;
            dup[i] = false;
        }
    }

    //idx자리에 새로운 newNum이 들어가는게 가능한지 검사
    public static  boolean isCorrect(char[] str, int[] ans, int idx, int newNum){
        if(idx == 0)
            return true;

        int oldNum = ans[idx-1];
        switch (str[idx-1]){
            case '<':
                if(oldNum<newNum)
                    return true;
                break;
            case '>':
                if(oldNum>newNum)
                    return true;
                break;
        }
        return false;
    }

    //std보다 num이 더 크면 true 반환, 아니면 false
    public static boolean isMax(int[] std, int[] num){
        for(int i=0; i<num.length; i++){
            if(std[i] == num[i])
                continue;
            if(std[i] < num[i])
                return true;
            else
                return false;
        }
        return false;
    }

    //std보다 num이 더 작으면 true 반환, 아니면 false
    public static boolean isMin(int[] std, int[] num){
        for(int i=0; i<num.length; i++){
            if(std[i] == num[i])
                continue;
            if(std[i] > num[i])
                return true;
            else
                return false;
        }
        return false;
    }
}

다른 풀이

import java.util.*;

public class Main {
    static int n;
    static char[] a = new char[20];
    static ArrayList<String> ans = new ArrayList<>();
    static boolean[] check = new boolean[10];
    static boolean good(char x, char y, char op) {
        if (op == '<') {
            if (x > y) return false;
        }
        if (op == '>') {
            if (x < y) return false;
        }
        return true;
    }
    static void go(int index, String num) {
        if (index == n+1) {
            ans.add(num);
            return;
        }
        for (int i=0; i<=9; i++) {
            if (check[i]) continue;
            if (index == 0 || good(num.charAt(index-1), (char)(i+'0'), a[index-1])) {
                check[i] = true;
                go(index+1, num+Integer.toString(i));
                check[i] = false;
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i=0; i<n; i++) {
            a[i] = sc.next().toCharArray()[0];
        }
        go(0, "");
        Collections.sort(ans);
        int m = ans.size();
        System.out.println(ans.get(m-1));
        System.out.println(ans.get(0));
    }
}

느낀점

backtracking을 이용하여 효율을 좀 더 높였다. 단계마다 가능한 자리인지 계산하였다. 가능하지 않다면 더이상 탐색이 의미없으므로 탐색을 중지하도록 했다.

---

시간복잡도: O(N의N승)

---

-최대, 최소값 구하는 새로운 방법

기존 나는 탐색 마지막에서 한요소씩 비교했다. 하지만 다른풀이처럼 ArraysList에 넣어놓고 정렬하면 맨앞뒤가 최대 최소값이니 더 깔끔하게 풀 수 있다.