[백준] 1107번 리모컨 (Java)

문제는 다음과 같다.

백준 1107 리모컨

dfs 활용해서 풀어보려고 했지만 정답율 30퍼에서 막혔고 결국 백트래킹을 활용했다. 숫자는 컸지만 시간복잡도가 O(n)이므로 하나하나 직접 비교해보는 방법도 고려해볼 수 있다. 더 큰 숫자에서 빼는 경우도 고려하기 위해서 0 ~ 999,999범위 내에서 탐색해야 한다.

import java.io.*;
import java.util.*;

public class Main {

    static int N;
    static boolean check [];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        // 예외 처리 신경 써야함
        if(n==0){
            int result = Math.abs(N - 100);
            result = Math.min(result,(String.valueOf(N).length()));
            System.out.println(result);
        }else{
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            check = new boolean[10];
            for (int i = 0; i < n; i++) {
                check[Integer.parseInt(st.nextToken())] = true;
            }
            System.out.println(solution());
        }
    }

    private static int solution() {
        int result = Math.abs(N - 100); 
        for (int i = 0; i <= 999999; i++) {
            String s = String.valueOf(i);
            if(isBroken(s)){
                result = Math.min(result,(s.length() + Math.abs(N-i)));
            }
        }
        return result;
    }

    private static boolean isBroken(String s) {
        for (int j = 0; j < s.length(); j++) {
            if(check[s.charAt(j)-'0']){
                return false;
            }
        }
        return true;
    }
}

완전 탐색을 더 연습할 필요가 있을 것 같다