AlgorithmBOJ

백준 부등호 2529

, , ,

1. 백준 부등호 2529 문제

1.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.2. 입력

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

1.3. 출력

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

1.4. 예제 입력 1

2
< >

1.5. 예제 출력 1

897
021

2. 컴퓨팅적 사고

  • 부등호의 개수가 주어지고 0~9까지의 값들을 가지고 해당 부등호 조건들이 만족하는 값들을 찾아 최댓값, 최솟값을 찾는 문제입니다.
  • 선택된 숫자는 모두 달라야하기때문에 값들을 체킹하는 변수가 필요해 보입니다. 그렇기 때문에 순열을 사용하면 되겠다 라는 생각을 하게 되었습니다.
  • K개의 부등호의 개수는 0~9까지의 값중 K+1개를 선택할 수 있는것과 같은 의미입니다.

입력으로 주어진 부등호 >, <에 따라 값 a,b가 만족하는지 찾는 함수가 필요합니다. 그리고 idx값이 0일때나 부등호가 성립하는경우에만 브루트포스를 사용하여 값을 순회합니다.idx값이 0일때 브루트포스를 순회하는 이유는 맨처음 문자열값이 ""으로 호출을 진행하기 때문에 이것에 대한 예외처리를 해준 것입니다.

문자열 완전탐색 문제는 어떻게 풀까?

  • 문제마다 다를 수 있겠지만 보통 브루트포스 문자열관련 문제가 나오게 되면 DFS호출시 문자열을 더하고 빼주는 형식으로 진행하는 것이 깔끔하고 구현이 더 쉽다고 생각합니다. 맨 처음에 문자열을 더하고 빼주는 형식으로 진행하지 않고 Basement조건이 만족했을때(return 조건) 처리를 하게 되면 복잡함을 느낄 수 있었습니다.

Basement 만족시
K+1개를 선택하여 DFS를 통해 모든 조건을 구하였던 문자열 값을 answer에 모든 값을 담아주게 하였습니다.

최댓값, 최솟값
문제에서 최댓값, 최솟값을 찾는 문제이므로 Collections.sort()함수를 사용하여 맨 앞(index=0), 맨뒤(answer.size()-1)의 값을 출력시켜주면 값을 도출해날 수 있습니다.

3. 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class 부등호문제 {
    static boolean[] check;
    static ArrayList<String> answer;
    static String inequality_sign = "";
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        check = new boolean[10];
        answer = new ArrayList<>();
        for(int i=0; i<k; i++){
            inequality_sign += st.nextToken();
        }

        dfs("", 0, k);
        Collections.sort(answer);

        System.out.println(answer.get(answer.size()-1) + "\n" + answer.get(0) + "\n");
    }

    private static void dfs(String s, int idx, int k) {
        // basement
        if(idx == k+1){
            answer.add(s);
            return;
        }
        for(int i=0; i<10; i++){

            if(check[i]){
                continue;
            }
            if(idx == 0 || inequality_check(s.charAt(idx-1), (i+'0'), inequality_sign.charAt(idx-1))){
                check[i] = true;
                dfs(s+String.valueOf(i), idx+1, k);
                check[i] = false;
            }
        }

    }
    // 부등호 체크 함수
    private static boolean inequality_check(int a, int b,char cal) {
        if(cal == '<'){
            if(a > b){
                return false;
            }
        }
        if(cal == '>'){
            if(a < b){
                return false;
            }
        }
        return true;
    }
}
Share