[백준/JAVA] 2529번 : 부등호(BruteFroce, 순열)

 

 

 

문제

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

2529번: 부등호

 

 

 

 

풀이

 

부등호가 k개 존재할 때, 부등호 앞 뒤로 숫자가 들어가게 되므로 숫자는 k+1개가 놓일 것이다.

어떤 부등호가 k개 쓰이든지 간에, k+1개의 숫자가 최대가 되려면 0부터 9까지의 정수 중 큰 k+1개의 정수만이 쓰여야 한다. 반대로, 최소가 되려면, 작은 k+1개의 정수만이 쓰여야 한다.

 

 

① 최댓값을 찾는 방법

• 가장 큰 수부터 시작하여 점점 작은 수를 탐색한다.
• 따라서 현재의 순열이 부등호의 조건을 만족하지 못하면, 이전 순열(작은 순열)을 찾아 탐색해야 한다.

② 최솟값을 찾는 방법

• 가장 작은 수부터 시작하여 점점 더 큰 수를 탐색한다.
• 따라서 현재의 순열이 부등호의 조건을 만족하지 못하면, 다음 순열(큰 순열)을 찾아 탐색해야 한다.

 

 

이 문제는 해를 찾을 때까지 이전/다음 순열을 찾아나가는 전체 탐색 문제이다. 선형 구조를 전체적으로 순차탐색하는 브루트포스로 해결할 수 있다. 브루트포스 알고리즘에 대해서는 아래 글에서 확인할 수 있다.

https://sy-zoze.tistory.com/12

[Algorithm] 브루트 포스(Brute Force) 알고리즘이란- 개념, 특징, 구현방법

 

 

먼저, 점점 더 작은 순열을 탐색하는 알고리즘을 구현하면 다음과 같다.

private static void prev_perm(int k, int[] max){

        int i = k;
        
        //오름차순의 시작점을 찾는다
        while(i>0 && max[i-1]<=max[i])
            i--;

        if(i<=0) return;	//가장 작은 값이므로 더 작은 순열은 존재하지 않는다

        int j = k;
        
        //i-1번째 수보다 작은 수 중 가장 큰 index를 가진 수를 찾는다
        while(max[j] >=max[i-1])
            j--;

        change(i-1, j, max);	//i-1번째 수와 j번째 수를 바꾼다
        
        //i번째 자리부터 내림차순이 되어야 한다
        j = k;
        while(i<j){
            change(i, j, max);
            i++;
            j--;
        }
    }

 

 

점점 더 큰 순열을 탐색하는 알고리즘을 구현하면 다음과 같다.

private static void next_perm(int k, int[] min){

        int i = k;
        
        //내림차순의 시작점을 찾는다
        while(i>0 && min[i-1]>=min[i])
            i--;

        if(i<=0) return;	//가장 큰 값이므로 더 큰 순열은 존재하지 않는다

        int j = k;
        
        //i-1번째보다 수보다 큰 수 중 가장 큰 index를 가진 수 찾는다
        while(min[j] <= min[i-1])
            j--;

        change(i-1, j, min);	//i-1번째 수와 j번째 수를 바꾼다
        
        //i번째 자리부터 오름차순이 되어야 한다
        j = k;
        while(i<j){
            change(i, j, min);
            i++;
            j--;
        }
}

 

 

구현한 알고리즘에 따라, 이전/다음 순열을 찾아가면서 부등호 조건을 만족하면 바로 탈출해야 한다.

이 때, 부등호 조건에 만족하는 수인지 확인하는 알고리즘은 다음과 같다.

private static boolean check(int[] arr, String[] sign){

		//부등호 조건이 하나라도 만족하지 않으면 바로 false
        for(int i = 0; i<arr.length-1; i++){
            if(sign[i].equals("<") && arr[i]>=arr[i+1]) return false;
            if(sign[i].equals(">") && arr[i] <= arr[i+1]) return false;
        }
        return true;	//모두 만족하면 true
}

 

 

 

 

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        String[] sign = new String[k];
        int[] result = new int[k+1];
        String max_result = "";
        String min_result = "";

        for(int i=0; i<k; i++){
            sign[i] = sc.next();
        }

        //큰 수 찾기
        for(int i = 9; i>=9-k; i--){
            result[9-i] = i;
        }


        while(true){
            if(check(result, sign)) break;
            prev_perm(k, result);
        }

        //큰 수 출력
        for(int i = k; i>=0; i--){
            max_result = max_result.concat(Integer.toString(result[k-i]));
        }

        //작은 수 찾기
        for(int i = 0; i<=k; i++){
            result[i] = i;
        }

        while(true){
            if(check(result, sign)) break;
            next_perm(k, result);
        }

        for(int i = k; i>=0; i--){
            min_result = min_result.concat(Integer.toString(result[k-i]));
        }

        System.out.println(max_result);
        System.out.println(min_result);
    }

    private static void prev_perm(int k, int[] max){

        int i = k;
        while(i>0 && max[i-1]<=max[i])
            i--;

        if(i<=0) return;

        int j = k;
        while(max[j] >=max[i-1])
            j--;

        change(i-1, j, max);
        j = k;
        while(i<j){
            change(i, j, max);
            i++;
            j--;
        }
    }

    private static void next_perm(int k, int[] min){

        int i = k;
        while(i>0 && min[i-1]>=min[i])
            i--;

        if(i<=0) return;

        int j = k;
        while(min[j] <= min[i-1])
            j--;

        change(i-1, j, min);
        j = k;
        while(i<j){
            change(i, j, min);
            i++;
            j--;
        }
    }

    private static boolean check(int[] arr, String[] sign){
        for(int i = 0; i<arr.length-1; i++){
            if(sign[i].equals("<") && arr[i]>=arr[i+1]) return false;
            if(sign[i].equals(">") && arr[i] <= arr[i+1]) return false;
        }
        return true;
    }

    private static void change(int i, int j, int[] result){
        int tmp = result[i];
        result[i] = result[j];
        result[j] = tmp;
    }
}

 

 

다른 방법

이 문제는 백트래킹 방법으로도 해결할 수 있다. 백트래킹 방법의 풀이는 아래 글에서 확인하면 된다.

https://sy-zoze.tistory.com/18

[백준/JAVA] 2529번 : 부등호(백트래킹, backtracking)