[백준] 2529번 부등호 (Java)

0. 출처

백준 2529번 문제입니다.

 

1. 문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

(1) 입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

(2) 출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.

 

2. 문제 풀이

(1) 문제 풀이 방법

부등호의 관계를 만족하는 최댓값과 최솟값을 찾는 문제입니다.

 

최댓값을 구하는 과정

1. 첫 번째 자리는 9부터 탐색

for(int i=9; i>=0; i--) { // i의 값을 첫 번째 자리 숫자로 사용
    if(maxFinish) break;

    numbers = new int[N+1];
    check = new boolean[10];
    check[i] = true;
    numbers[0] = i;
    findMax(1, numbers);
}

2-1. 부등호가 "<" 일 경우 무조건 9부터 1씩 줄여가며 탐색 시작

if(s.equals("<")){
    for(int i=9; i>pre; i--) { // 최댓값을 구하는 것이므로 무조건 9부터 탐색 시작
        if(!check[i]) {
            numbers[depth] = i;
            check[i] = true;
            findMax(depth+1, numbers);
            check[i] = false;
        }
    }
}

2-2. 부등호가 ">"일 경우 pre-1부터 1씩 줄여가며 탐색 시작 

else {
    for(int i=pre-1; i>=0; i--) {
        if(!check[i]) {
            numbers[depth] = i;
            check[i] = true;
            findMax(depth+1, numbers);
            check[i] = false;
        }
    }
}

 

최솟값을 구하는 과정

1. 첫 번째 자리는 0부터 탐색

for(int i=0; i<10; i++) { // i의 값을 첫 번째 자리 숫자로 사용
    if(minFinish) break;

    numbers = new int[N+1];
    check = new boolean[10];
    check[i] = true;
    numbers[0] = i;
    findMin(1, numbers);
}

2-1. 부등호가 "<" 일 경우 pre+1부터 1씩 더해가며 탐색 시작

if(s.equals("<")){
    for(int i=pre+1; i<10; i++) {
        if(!check[i]) {
            numbers[depth] = i;
            check[i] = true;
            findMin(depth+1, numbers);
            check[i] = false;
        }
    }
}

2-2. 부등호가 ">"일 경우 무조건 0부터 1씩 더해가며 탐색 시작 

else {
    for(int i=0; i<pre; i++) { // 최솟값을 구하는 것이므로 무조건 0부터 탐색 시작
        if(!check[i]) {
            numbers[depth] = i;
            check[i] = true;
            findMin(depth+1, numbers);
            check[i] = false;
        }
    }
}

(2) 코드 (Java)

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

public class Main {
    static int N;
    static String[] sign;
    static boolean[] check;
    static int[] numbers;
    static String minValue;
    static boolean minFinish = false;

    static String maxValue;
    static boolean maxFinish = false;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        sign = new String[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            sign[i] = st.nextToken();
        }
        
        for(int i=9; i>=0; i--) { // 최댓값 구하기
            if(maxFinish) break;
            
            numbers = new int[N+1];
            check = new boolean[10];
            check[i] = true;
            numbers[0] = i;
            findMax(1, numbers);
        }
        System.out.println(maxValue);

        for(int i=0; i<10; i++) { // 최솟값 구하기
            if(minFinish) break;
            
            numbers = new int[N+1];
            check = new boolean[10];
            check[i] = true;
            numbers[0] = i;
            findMin(1, numbers);
        }
        System.out.println(minValue);
        
        br.close();
    }

    static void findMax(int depth, int[] numbers) {
        if(maxFinish) return;

        if(depth == N+1) {
            String max = "";
            for(int n: numbers) {
                max += n;
            }
            maxValue = max;
            maxFinish = true;
            return;
        }
        
        String s = sign[depth-1];
        int pre = numbers[depth-1];
        if(s.equals("<")){ // 앞의 숫자보다 큰 숫자가 와야할 때
            for(int i=9; i>pre; i--) { // 최댓값을 구하는 것이므로 무조건 9부터 탐색
                if(!check[i]) {
                    numbers[depth] = i;
                    check[i] = true;
                    findMax(depth+1, numbers);
                    check[i] = false;
                }
            }
        } else { // 앞의 숫자보다 작은 숫자가 와야할 때
            for(int i=pre-1; i>=0; i--) { 
                if(!check[i]) {
                    numbers[depth] = i;
                    check[i] = true;
                    findMax(depth+1, numbers);
                    check[i] = false;
                }
            }
        }
    }
    
    static void findMin(int depth, int[] numbers) {
        if(minFinish) return;

        if(depth == N+1) {
            String min = "";
            for(int n: numbers) {
                min += n;
            }
            minValue = min;
            minFinish = true;
            return;
        }
        
        String s = sign[depth-1];
        int pre = numbers[depth-1];
        if(s.equals("<")){ // 앞의 숫자보다 큰 숫자가 와야할 때
            for(int i=pre+1; i<10; i++) { 
                if(!check[i]) {
                    numbers[depth] = i;
                    check[i] = true;
                    findMin(depth+1, numbers);
                    check[i] = false;
                }
            }
        } else { // 앞의 숫자보다 작은 숫자가 와야할 때
            for(int i=0; i<pre; i++) { // 최솟값을 구하는 것이므로 무조건 0부터 탐색
                if(!check[i]) {
                    numbers[depth] = i;
                    check[i] = true;
                    findMin(depth+1, numbers);
                    check[i] = false;
                }
            }
        }
    }
}

 

(3) 결과