🔥[99클럽 코테 스터디] 37일차 TIL - 부등호

⏳문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 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
< >

출력

897
021

---

입출력 예 2

입력

9
> < < < > > > < <

출력

9567843012
1023765489

---

✏️풀이

이 문제를 풀기 위해서는 0부터 9까지의 숫자들로 조합을 만들고,
조합한 순열이 주어진 부등호 조건을 만족하는 지 확인해나가면 된다.
단, 각 숫자는 한 번만 사용할 수 있으므로, 중복을 피해야 한다.

나는 모든 가능한 숫자 조합을 백트래킹(backtracking) 기법을 통해 생성해보고, 조건에 부합하는 순열을 찾아내 그 중 최대, 최소값을 최종적으로 반환하여 문제를 해결하였다.

모든 경우의 수를 고려해야 하기 때문에, 시간 초과 문제가 있지 않을까 생각을 해 보았는데, 사용할 숫자에 중복이 없고, k의 범위가 정해져 있어 완전 탐색을 해도 문제가 없을 것이라 생각했다.

👾전체 코드

import java.util.*;

public class Baekjoon_2529 {
    static boolean[] visited = new boolean[10]; // 방문 여부
    static String[] num = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}; // 사용 가능한 숫자
    static int count; // 입력받을 부등호 개수
    static String[] input; // 입력받을 부등호
    static ArrayList<String> result = new ArrayList<>(); // 결과 리스트

    static void permutation(int index, String now) {
        // 순열을 다 만들었을 경우
        // 현재까지 만든 숫자 조합 now가 부등호 조건을 만족하는 지 확인
        if (index == count + 1) {
            // 부등호 조건을 만족한다면 결과 리스트에 추가
            if (check(now)) {
                result.add(now);
            }
            return;
        }

        // 순열 만들기
        for (int i = 0; i < 10; i++) {
            if (!visited[i]) {
                visited[i] = true;
                permutation(index + 1, now + num[i]);
                visited[i] = false; // 백트래킹을 위해 미방문 처리
            }
        }
    }

    // 부등호 조건 확인
    static boolean check(String temp) {
        for (int i = 0; i < count; i++) {
            int a = temp.charAt(i) - '0';
            int b = temp.charAt(i + 1) - '0';
            
            // 부등호 조건에 맞지 않으면 false 반환
            if (input[i].equals(">") && a < b) {
                return false;
            }
            if (input[i].equals("<") && a > b) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        count = sc.nextInt(); // 개수 입력
        input = new String[count];

        // 부등호 입력
        for (int i = 0; i < count; i++) {
            input[i] = sc.next();
        }

        permutation(0, "");
        System.out.println(result.get(result.size() - 1));
        System.out.println(result.get(0));

        sc.close();
    }
}

👾코드 설명

1. 부등호의 개수를 count에 입력받고, input배열에 부등호의 정보를 입력받는다.

2. 순열을 생성해 나가는 메서드인 permutation을 실행한다. permutation 메서드는 현재까지 선택한 숫자의 개수를 나타내는 index와 현재까지 선택한 숫자를 문자열로 저장하는 now를 매개변수로 받는다.

3. 현재 문자열 now의 길이가 부등호 조건의 길이 + 1이 될 때까지 순열을 생성해 나간다.

4. 순열을 다 만들었을 경우 부등호 조건에 부합하는 지 확인하기 위해 check메서드를 호출한다.

5. check메서드에서 부등호 조건에 부합한다면, true를 반환해 결과 리스트 result에 해당 순열을 저장한다.

6. 백트래킹을 통해 중복되지 않는 순열을 계속 생성해 나가며, 4~5번 과정을 반복해 조건에 부합하는 순열을 result에 계속해서 저장한다.

7. 순열을 오름차순으로 만들었기 때문에, result의 마지막 요소가 조건에 부합하는 순열 중 최대값이 되고, 첫 번째 요소가 최소값이 된다.

---

🔗문제 링크
💻Repository