백준 2529번 부등호 :: 마이구미

이 글은 백준 알고리즘 문제 2529번 "부등호" 를 풀이한다.

정올 초등부에서 출제된 문제이다.

본인은 백트래킹을 활용해서 문제를 해결했다.

문제 링크 - https://www.acmicpc.net/problem/2529

두 종류의 부등호 기호 ‘<’와 ‘>’가 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 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.

문제는 각 부등호에 넣을 수 있는 수를 구하는 것이다.

부등호에 성립하는 수를 구하면서, 각 숫자는 중복되지 않는다는 점을 기억해야한다.

구해지는 수는 여러 개가 존재할 수 있는데, 그 중 최대값과 최소값을 구해야한다.

조금 까다로울 수도 있으나, 모든 경우를 탐색한다면 쉽게 해결할 수 있다.

k의 갯수가 최대 10 이기 때문에, 모든 경우를 탐색해도 시간초과 걱정은 없다.

DFS 를 통해 탐색하고, 모든 경우를 위해 백트래킹을 활용한다.

백트래킹은 간단히 다음과 같은 그림으로 나타낼 수 있다.

그 과정속에서 부등호에 대한 조건과 수가 중복 여부를 체크하면서 탐색해주면 된다.

탐색하는 과정속에서 탐색된 수가 k + 1 개가 되면, 부등호에 맞는 수가 완성된 것이다.

반대로 그렇지 않다면, 불완전한 수이기 때문에 걸러주면 된다.

기본적인 백트래킹을 활용한 DFS 에서 탐색 조건만 추가된 것이다.

자세한 건 어렵지 않게 코드를 통해 이해할 수 있을 것이다.

관련 문제 - http://mygumi.tistory.com/191?category=689692

Github - https://github.com/hotehrud/acmicpc/tree/master/graph

static boolean[] visited = new boolean[10];
static ArrayList<String> list = new ArrayList<String>();
static String[] input;
static int k;
 
private void solve() {
    k = sc.nextInt();
    input = sc.readLine().split(" ");
 
    for (int i = 0; i <= 9; i++) {
        visited[i] = true;
        dfs(i, 0, i + "");
    }
    System.out.println(list.get(list.size() - 1));
    System.out.println(list.get(0));
}
 
public static void dfs(int v, int cnt, String str) {
    if (cnt == k) {
        // success
        list.add(str);
    } else {
        for (int i = 0; i <= 9; i++) {
            if (!visited[i]) {
                if (input[cnt].equals("<")) {
                    if (v >= i) {
                        continue;
                    }
                } else {
                    if (v <= i) {
                        continue;
                    }
                }
                visited[i] = true;
                dfs(i, cnt + 1, str + i);
            }
        }
    }
    // backtracking
    visited[v] = false;
}