[JAVA] 백준 2529_부등호

[문제링크]

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

 

📌 문제 탐색하기

k개의 부동호를 입력받았을때 0-9까지 숫자중에서 입력받은 k개의 부등호 숫자보다 1개 큰 k+1개의 서로 다른 숫자를 골라서 주어진 부등호 조건을 만족하는 숫자 조합들 중에서 가장 큰 숫자와 가장 작은 숫자를 출력하는 문제이다.  

예제입력1을 보면 2 <> 가 입력되었을때, 가능한 경우의 수는

0 < 1 > 0  ( 숫자 0 중복 사용으로 불가능 )  

1 < 2 > 0    ( 가능 )   => 120

1 < 2 > 1 ( 숫자 1 중복 사용으로 불가능 )  => 121

2 < 3 > 1     ( 가능 )  => 231 

2 < 3 > 0     ( 가능 )  => 230 

....

8 < 9 > 7     ( 가능 )  => 897

이런식으로 숫자조합이 생성되며 이때 조합 가능한 가장 큰 숫자는 : 897 이고 가장 작은 숫자는 : 021이다. 

따라서 897과 021을 출력한다. 

📌 코드 설계하기

[ 백트래킹 ] 

하나씩 숫자를 골라서 조건을 만족하는지 확인하는 알고리즘 방식 사용.

예시1에서 처럼 입력된 부등호가  < > 이라면, 0 - 9중에서 첫번째 숫자를 고르고 체크,  중복되지 않는 다른 숫자를 골라서 부등호 조건이 성립하는지 확인하고 체크, 만약에 부등호 조건이 성립되지 않으면 백트래킹으로 이전 단계로 돌아가서 다시 다른 숫자 골라서 확인하는 방식 반복! 입력받은 부등호의 개수는 k이니까 k+1개의 숫자를 모두 골랐으면 종료하고 최댓값이랑 최솟값 출력하면 된다. 

📌 가능한 시간복잡도 

 백트래킹을 활용하는 문제이니까 시간복잡도에서도 재귀호출을 활용함. 각각 숫자를 하나씩 선택하고 다음 숫자를 선택하는 방식이니까 깊이가 k+1인 트리구조이다. 숫자는 총 k+1개 선택해야 하니까 백트래킹의 최대 깊이는 k+1입니다.  이때 숫자는 중복 없이 모두 다른 숫자를 선택해야하니까 1번 순서는 0-9까지 10가지 선택지가 있고 그 다은에는 9가지...8가지.. 1씩 줄어든다. 즉, 10*9*8*7...(10-k)이니까 순열 개수 구하는 공식인 10! / (10-k)! 이므로 가능한 시간 복잡도는 O( 10! / (10-k)! ) 이라고 생각합니다. 

📌 정답 코드

import java.util.*;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt(); 
        signs = new char[k]; 
        
        for (int i = 0; i < k; i++) {
            signs[i] = sc.next().charAt(0); 
        }

        findNumbers("", 0); 

        Collections.sort(results); 

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

    static void findNumbers(String num, int depth) {
        if (depth == k + 1) { 
            results.add(num); 
            return;
        }

        for (int i = 0; i < 10; i++) { 
            if (!used[i]) {
                if (depth == 0 || isValid(num.charAt(depth - 1) - '0', i, signs[depth - 1])) {
                    used[i] = true;
                    findNumbers(num + i, depth + 1); 
                    used[i] = false;
                }
            }
        }
    }

    static boolean isValid(int prev, int next, char sign) {
        if (sign == '<') return prev < next;
        return prev > next;
    }
}