2529 부등호

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	15816	8388	5672	51.335%

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 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가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다.

출력

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

예제 입력 1

2
< >

예제 출력 1

897
021

예제 입력 2

9
< < < > > > < <

예제 출력 2

9567843012
1023765489

코드

import java.io.*;

public class P_2529 {
    static int k;
    static String[] inequality_sign;
    static String max = Long.toString(Long.MIN_VALUE);
    static String min = Long.toString(Long.MAX_VALUE);

    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());
        inequality_sign = br.readLine().split(" ");

        find_integer("", 0, 0);
        bw.write(max);
        bw.newLine();
        bw.write(min);
        bw.flush();
    }

    public static void find_integer(String res, int idx, int digit) {
        if (idx == k) {
            if (max.compareTo(res) < 0) max = res;
            if (min.compareTo(res) > 0) min = res;
        }
        else {
            for (int i = 0; i <= 9; i++) {
                if (!overlap(res, i)) {
                    if (digit == 0) {
                        res = Integer.toString(i);
                        find_integer(res, idx, digit + 1);
                    } else {
                        if ((inequality_sign[idx].equals(">") && res.charAt(res.length() - 1) - '0' > i)
                                || (inequality_sign[idx].equals("<") && res.charAt(res.length() - 1) - '0' < i)) {
                            find_integer(res + Integer.toString(i), idx + 1, digit + 1);
                        }
                    }
                }
            }
        }
    }

    public static boolean overlap(String res, int num) {
        for (int i = 0; i < res.length(); i++) {
            if (res.charAt(i) - '0' == num)
                return true;
        }
        return false;
    }
}

코드 설명

재귀 함수의 인자 중 idx는 부등호 배열을 참조하는 인덱스이고, digit는 현재 만든 정수인 res의 자릿수를 저장하는 배열이다.
부등호는 수와 수 사이에 들어가기 때문에 하나의 정수 변수로 두 가지를 모두 참조하기 어렵기 때문에 나눠서 저장했다.

digit이 0일 땐 idx를 쓸 이유가 없고 그냥 res를 업데이트만 해주면 되기 때문에 digit이 0일 때와 아닐 때로 조건을 구분했다.

재귀 함수를 호출할 때마다 i가 0부터 9까지 카운팅되기 때문에 중복을 걸러줄 수 없어 해당 함수를 따로 추가해 체크를 해 주었고 수마다 모두 체크를 해서 중복이 아닐 경우만 res를 업데이트할 수 있는 기회를 주었다.
이 부분의 경우 visited 배열을 만들어서 사용하는게 더 효율적이라고 생각했지만 성능상 큰 문제가 없어 구현/생각하기 쉬운 방식을 택했다.

첫 제출 때 max와 min의 초기화를 각각 Integer.MIN_VALUE, Integer.MAX_VALUE로 했는데 k가 9일 때 답이 제대로 도출되지 않는 문제가 있었다.
k가 9이면 구해야 하는 정수의 자릿수는 총 10이된다.
int의 최댓값은 2147483647로 10자리 수인데 k가 9일 때 최댓값은 9876543210이 나올 수 있어서 기준값을 잘못 잡은 꼴이 되어버린다.
위 코드는 max, min변수를 String으로 선언해서 오류가 발생하지는 않았고 그저 이상한 답만 도출될 뿐이지만 int변수로 쓸 경우 오류가 발생하면서 프로그램이 종료되게 된다.
그래서 9876543210을 커버할 수 있는 Long 자료형을 썼다.