[99클럽 5기 코테 스터디 TIL 13일차] 부등호 (feat. 완전탐색 - 백트래킹)

1) 문제

https://www.acmicpc.net/problem/2529

 

 

2) 문제 풀이

import java.util.*;

public class Main {
    static int k;
    static char[] signs;
    static boolean[] visited = new boolean[10];
    static List<String> results = new ArrayList<>();
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt();
        signs = new char[k];
        
        for (int i = 0; i < k; i++) {
            signs[i] = sc.next().charAt(0);
        }
        
        dfs("", 0);
        
        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 + 1) {
            results.add(num);
            return;
        }
        
        for (int i = 0; i <= 9; i++) {
            if (!visited[i]) {
                if (depth == 0 || check(num.charAt(depth - 1) - '0', i, signs[depth - 1])) {
                    visited[i] = true;
                    dfs(num + i, depth + 1);
                    visited[i] = false;
                }
            }
        }
    }
    
    static boolean check(int a, int b, char sign) {
        return (sign == '<') ? (a < b) : (a > b);
    }
}

설명:

1. 입력 처리: Scanner를 사용하여 k와 부등호 배열을 입력받음
2. 백트래킹 탐색:
   • dfs 함수는 가능한 숫자 조합을 찾아감
   • visited 배열을 사용하여 중복을 방지함
   • check 함수는 부등호 관계를 만족하는지 확인함
3. 결과 정렬 및 출력:
   • 가능한 모든 조합을 리스트에 저장한 후 정렬하여 최댓값과 최솟값을 출력함

시간 복잡도:

백트래킹을 사용하여 최적의 탐색을 수행하므로, 가능한 숫자 조합을 효율적으로 찾을 수 있음