99클럽 코테 스터디 37일차 TIL - [백준] 2529번: 부등호 (Java)

📌 오늘의 학습 키워드

[백준] 2529번: 부등호 (Java)
https://www.acmicpc.net/problem/2529

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 첫번째 줄-부등호 문자의 개수 k
두번째 줄-k개의 부등호 기호 (공백으로 구분)
출력 : 첫번째 줄-부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수
두번째 줄-부등호 관계를 만족하는 k+1 자리의 최소 정수

가능한 시간복잡도

O(n!)

알고리즘 선택

dfs

📌 코드 설계하기

1. 먼저 k를 입력받고, k개의 부등호를 배열 operators에 저장한다.
2. dfs 함수는 현재까지의 숫자 조합 num과 깊이 depth를 매개변수로 받아 백트래킹을 진행한다.
3. 숫자 i를 선택하여 조건에 맞으면 다음 단계로 이동하고, k 길이에 도달하면 해당 숫자 조합을 results 리스트에 추가한다.
4. check 함수는 부등호 조건을 확인하는 함수로, 현재 숫자와 다음에 선택할 숫자가 주어진 부등호를 만족하는지 확인한다.
5. 모든 가능한 조합을 results 리스트에 추가한 후, 이를 정렬하여 최대값과 최소값을 출력한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

public class Main {

    static int k;
    static char[] operators;
    static boolean[] visited = new boolean[10];
    static ArrayList<String> results = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        k = scanner.nextInt();
        operators = new char[k];

        for (int i = 0; i < k; i++) {
            operators[i] = scanner.next().charAt(0);
        }

        // 백트래킹을 사용하여 가능한 모든 숫자 조합을 만듦
        for (int i = 0; i <= 9; i++) {
            visited[i] = true;
            dfs("" + i, 0);
            visited[i] = false;
        }

        // 가능한 결과를 정렬하여 최소값과 최대값을 찾음
        Collections.sort(results);
        System.out.println(results.get(results.size() - 1)); // 최대값 출력
        System.out.println(results.get(0)); // 최소값 출력
    }

    static void dfs(String num, int depth) {
        if (depth == k) {
            results.add(num);
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (!visited[i] && check(num.charAt(num.length() - 1) - '0', i, operators[depth])) {
                visited[i] = true;
                dfs(num + i, depth + 1);
                visited[i] = false;
            }
        }
    }

    static boolean check(int a, int b, char op) {
        if (op == '<') {
            return a < b;
        } else {
            return a > b;
        }
    }
}