알고리즘 풀이 - 백준 2529(부등호, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

주어진 부등호 기호에 맞게 숫자를 나열 후 부등호를 제외한 숫자만으로 이루어진 내역 중 최대 / 최소값을 고르는 문제

 

 

2. 풀이

 

입력을 통해 부등호의 개수와 그 개수 만큼의 부등호가 주어진다.

부등호의 개수는 모두 K개가 주어지며, 부등호의 사이 사이와 제일 좌측 / 우측에 숫자를 부등호 조건에 맞게 놓을 수 있는 모든 숫자의 경우를 찾아야 한다.

예를 들면 문제에 주어진 경우와 같이 예시를 들 수 있다.

예시

 

부등호의 개수 +1개의 모든 숫자를 테스트하여야 하는데 숫자는 최대 0~9까지 10개 있을 수 있으니 재귀를 통해 완전 탐색을 수행하여 가능한 숫자를 모두 찾아야 한다.

단순히 10개의 숫자를 나열한다면 10! = 3628800 이므로 완전 탐색으로 충분히 풀 수 있다.

 

재귀로 풀기 위해서는 우선 탈출 조건과 함수의 상태(Parameter)를 결정해야 한다.

우선, 탈출 조건은 다음과 같을 것이다.

① K+1개의 숫자가 모두 정해진 경우
② 부등호 조건을 만족하지 않는 경우

 

그렇다면 탈출 조건을 결정하기 위해서 현재 함수의 상태에 전달할 값은 다음과 같을 것이다.

① 현재 결정된 숫자의 개수
② 현재 까지 이어진 숫자의 문자열

Parameter에 ②는 왜 필요할까? 문제에 따르면 0으로 시작하는 숫자도 있을 수 있기 때문이다. 물론 전달하지 않고 최초 부등호가 <라면 무조건 제일 좌측을 0으로 설정해도 된다.(이렇게 해도 문제가 해결된다.)

 

그런데, 이 문제에서는 부등호라는 조건이 있기 때문에 매 재귀 때마다 현재 사용하지 않은 숫자를 모두 탐색할 필요가 없다. 이전에 선택된 숫자를 기반으로 현재 부등호 조건에 맞는 숫자 중 남는게 있는지만 판단하면 된다!

위 방법으로 시간복잡도도 줄여보자!

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;

public class Main{
    static int k;
    static String[] sign;
    static boolean[] visited;
    static String max = "";
    static String min = "";
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        k = Integer.parseInt(br.readLine());
        sign = br.readLine().split(" ");
        visited = new boolean[10];

        // max, min값을 우선 초기화(k+1개의 0 또는 9로 초기화)
        for(int i=0; i <= k; i++){
            max += 0;
            min += 9;
        }

        solve(0, "");

        bw.write(max + "\n" + min);
        bw.flush();
        br.close();
    }


    private static void solve(int idx, String str){
        // k+1개의 숫자를 모두 선택했다면 숫자를 비교 후 최대 / 최소 값 업데이트
        if(idx == k+1) {
            compare(str);
            return;
        }
        
        // direction은 부등호에 따라 < 면 이전 수보다 높은 수만, > 면 낮은 수만 비교하도록
        // 방향성을 결정하는 부분. 그러나 idx 값이 0이면 제일 처음 수행되는 것이므로 
        // 무조건 1로 지정한다. 또한 sign은 k개가 있는데 최초 idx값이 0이 전달되고 1부터 시작되니
        // idx-1로 지정한다.
        int direction = idx == 0 || sign[idx-1].equals("<") ? 1 : -1;
        
        // start는 현재까지 결정된 숫자 중 가장 마지막 값을 찾아 direction을 더하는 변수
        // 만약 아무 결정된 숫자가 없다면 0으로 초기화
        int start = idx == 0 ? 0 : str.charAt(idx-1) - '0' + direction;

        // i값은 start 부터 시작하여 숫자를 결정 짓고 재귀를 수행한다.
        for(int i=start; i >= 0 && i <= 9; i += direction){
            if(!visited[i]){
                visited[i] = true;
                solve(idx+1, str+i);
                visited[i] = false;
            }
        }
    }

    // 최대 / 최소값 비교
    private static void compare(String str){
        int i=0;
        int j=0;
        while(str.charAt(i) == max.charAt(i)) i++;
        if(i <= k && str.charAt(i) > max.charAt(i)) max = str;

        while(str.charAt(j) == min.charAt(j)) j++;
        if(j <= k && str.charAt(j) < min.charAt(j)) min = str;
    }
}

 

그런데 위 방식은 string 비교 부분 때문인지 시간이 많이 걸린다. 따라서 아래와 같이 다른 코드로 해결하니 기존의 절반 정도의 시간으로 해결할 수 있었다.

 

아래는 숫자 그 자체로 비교를 하되, 제일 앞의 부등호가 "<"라면 앞에 0을 무조건 붙이는 방식으로 수행하였다.

import java.io.*;

public class Main{
    static int k;
    static String[] sign;
    static boolean[] visited;
    static long max = 0;
    static long min = Long.MAX_VALUE;
    static int[] chosen;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        k = Integer.parseInt(br.readLine());
        sign = new String[k];
        visited = new boolean[10];
        chosen = new int[k+1];

        sign = br.readLine().split(" ");

        // 여기서는 숫자 하나를 여기서 먼저 결정하고 시작
        // 그래서 solve 함수에서 idx-1등 처리가 불필요
        for(int i=0; i <= 9; i++){
            chosen[0] = i;
            visited[i] = true;
            solve(i, 0);
            visited[i] = false;
        }

        bw.write(max + "\n");

        // 가장 먼저 나오는 부등호가 < 면 0을 붙인다.
        if(sign[0].equals("<")){
            bw.write(String.valueOf(0));
        }
        bw.write(String.valueOf(min));
        bw.flush();
        br.close();
    }


    private static void solve(int n, int idx){
        if(idx == k){
            long num = 0;
            for(int i=0; i < k+1; i++){
                num += chosen[i] * (long)Math.pow(10, k-i);
            }
            max = Math.max(max, num);
            min = Math.min(min, num);
            return;
        }

        // 방향성 설정하고 어떤 값부터 시작할지 결정
        int direction = sign[idx].equals("<") ? 1 : -1;
        int i = sign[idx].equals("<") ? n+1 : n-1;

        for(; i >= 0 && i <= 9; i+=direction){
            if(!visited[i]) {
                visited[i] = true;
                chosen[idx+1] = i;
                solve(i, idx+1);
                visited[i] = false;
            }
        }
    }
}

 

 

4. 추가

 

이 문제는 순열로도 풀 수 있다. 순열은 완전 탐색 포스팅(여기)를 참고하여 만드는 방법을 알아보자.

K개의 부등호가 주어질 때, K+1개의 숫자를 이용해 최소 / 최대값을 구하고 그 결과를 출력하면 되므로 각각의 경우에 숫자를 고르고 다음 순열 / 이전 순열을 구하면서 부등호에 부합한다면 출력하는 식으로 구현하였다.

 

순열로 풀어보기

import java.io.*;

public class Main{
    static int k;
    static String[] sign;
    static boolean[] visited;
    static long max = 0;
    static long min = Long.MAX_VALUE;
    static int[] chosen;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        k = Integer.parseInt(br.readLine());
        sign = new String[k];
        visited = new boolean[10];
        chosen = new int[k+1];

        sign = br.readLine().split(" ");

        // ************************ 최대값을 구하는 코드 **********************
        // 최대값을 구하기 위해 k+1개의 숫자를 선택한다.
        // (9-k) ~ 9 까지의 숫자를 선택하고 그 안에서 완전탐색을 수행
        int idx = 0;
        for(int i=9; i >= 9-k; i--){
            chosen[idx] = i;
            idx++;
        }
        
        // 올바른 경우의 수를 찾을 때까지 다음 순열을 찾는다.
        while(true){
            if(check()) break;
            get_prev_perm();
        }

        for(int i=0; i <= k; i++){
            sb.append(chosen[i]);
        }
        sb.append("\n");
        // ************************ 최대값 구하기 완료 ************************


        // *********************** 최소값을 구하는 코드 ************************
        // 최소값을 구하기 위해 k+1개의 숫자를 선택한다.
        // 0~k+1 까지의 숫자를 선택하고 그 안에서 완전탐색을 수행
        for(int i=0; i <= k; i++){
            chosen[i] = i;
        }
        
        // 올바른 경우의 수를 찾을 때까지 다음 순열을 찾는다.
        while(true){
            if(check()) break;
            get_next_perm();
        }

        for(int i=0; i <= k; i++){
            sb.append(chosen[i]);
        }
        // ************************ 최소값 구하기 완료 ************************
        
        
        System.out.println(sb);
        br.close();
    }
    
    // 이전 순열을 구하는 코드
    private static void get_prev_perm(){
        int i = k;
        while(i > 0 && chosen[i-1] <= chosen[i]) i--;
        if(i <= 0) return;
        
        int j=i;
        while(j < k && chosen[i-1] > chosen[j+1]) j++;
        
        swap(i-1, j);
        j = k;
        while(i < j){
            swap(i, j);
            i+=1; j-=1;
        }
    }

    // 다음 순열을 구하는 코드
    private static void get_next_perm(){
        int i = k;
        while(i > 0 && chosen[i-1] >= chosen[i]) i--;
        if(i <= 0) return;
        
        int j=i-1;
        while(j < k && chosen[j+1] > chosen[i-1]) j++;
        
        swap(i-1, j);
        j = k;
        while(i < j){
            swap(i, j);
            i+=1; j-=1;
        }
    }

    // 현재 숫자가 부등호에 부합하는지 체크하는 코드
    private static boolean check(){
        for(int i=0; i < k; i++){
            if(sign[i].equals("<") && chosen[i] >= chosen[i+1]) return false;
            if(sign[i].equals(">") && chosen[i] <= chosen[i+1]) return false;
        }
        return true;
    }
    
    // 배열 내 swap을 수행하는 코드
    private static void swap(int i, int j){
        int temp = chosen[i];
        chosen[i] = chosen[j];
        chosen[j] = temp;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.