[백준/JAVA] 1107번 리모컨 - BruteForce

풀이

고장난 버튼 저장 방식

고장난 버튼을 미리 저장해둔다.
나중에 입력된 버튼이 고장난 버튼인지 찾기 위해서 for문을 돌리는 순간, 시간초과 확정이다.
이를 위해서 고장난 버튼을 boolean 형으로 저장한다.

입력된 버튼 파싱 방법

%10을 하면 입력된 버튼의 값이

/10을 하면 다음 버튼의 값이 1의 자릿수로 설정되고 이를 %10하면 버튼의 값이 무엇인지 알 수 있다.

원하는 채널 중에 가장 근삿값은?

초기 채널은 100번이다. 앞으로 4000번을 틀기 위해서 10개의 버튼이 모두 고장나있는 경우 3900번을 눌러야 한다는 의미이다.

여기서 3900번과

내가 임의로 값을 지정해서 그 입력할 값에 이상이 있는지 없는지를 판단하고 위에서 3900번과 비교를 한다.

이미 N-100을 진행했으므로, 0과 가장 가까운 값 Math.min을 통해 판별한다.

코드

제출 코드

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

class Main {

    static int N, M;
    static boolean[] broken;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        broken = new boolean[10];

        if (M != 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < M; i++) {
                broken[Integer.parseInt(st.nextToken())] = true;
            }
        }


        int result = Math.abs(N - 100);
        for (int i = 0; i < 1000000; i++) {
            if (check(i) != 0) {
                result = Math.min(result, Math.abs(N - i) + check(i));
            }
        }
        bw.write(String.valueOf(result));
        bw.flush();
    }

    public static int check(int n) {
        if (n == 0) return broken[0] ? 0 : 1;

        int cnt = 0;

        while (n > 0) {
            if (broken[n % 10]) return 0;

            n /= 10;
            cnt++;
        }
        return cnt;
    }
}