문제

풀이 1

이해

크게 채널을 이동할 수 있는 방법은 두 가지이다. 첫번째는 현재 채널 100번에서 직접 이동하는 것이고, 두번째는 목표 채널과 가장 가깝고 입력 가능한 채널로 이동 후에 직접 이동하는 것이다.

첫번째 방법의 경우에는 |N - 100|으로 쉽게 구할 수 있다.

두번째 방법의 경우에는 까다로운데 bias를 통해 구하기로 하였다. 목표 값에서 bias만큼 거리가 있는 채널이 입력 가능한지 확인하고 가능하다면 해당 채널을 입력하고 직접 하는 것이 최소값이 될 수 있다.

코드

package java_baekjoon;

import java.io.IOException;
import java.util.Scanner;

public class prob1107 {
    static int N;
    static int M;
    static boolean button[];

    public static void main(String[] args) throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        button = new boolean[10];

        for (int i = 0; i < 10; i++) {
            button[i] = true;
        }
        for (int i = 0; i < M; i++) {
            button[sc.nextInt()] = false;
        }
        int ans = 0;

        int bias = 0; // N에서의 거리

        while (true) { // bias만큼 떨어진 거리의 채널이 가능한지를 검색
            if (check(N + bias)) {
                ans = bias + (int) (Math.log10(N) + 1);
                break;
            }

            if (check(N - bias) && (N - bias) >= 0) {
                ans = bias + (int) (Math.log10(N) + 1);
                break;
            }
            bias++;
        }
        if (ans <= (Math.abs(N - 100))) { // 100에서 직접 이동과 비교 후 작은 값 선택
            System.out.println(ans);
        } else {
            System.out.println((Math.abs(N - 100)));
        }
        sc.close();
    }

    public static boolean check(int n) { // 가능한 채널인지 체크
        String str = String.valueOf(n);

        for (int i = 0; i < str.length(); i++) {
            if (!button[str.charAt(i) - '0']) {
                return false;
            }
        }
        return true;
    }
}

결과

예제 입출력과 다른 오류는 없는 것 같으나 런타임 에러가 발생한다. 원인을 찾는 중이다.

풀이2

이해

본 문제는 완전 탐색으로도 풀 수 있다. 채널의 수는 0~500000으로 탐색 범위가 한정되어 있기 때문에 시간복잡도도 그다지 크지 않다.

범위의 채널을 차례로 검사하여 입력 가능 여부를 판단하고 만일 가능하다면 입력 횟수 값을 계산한다. 반복할 때마다 이전 (혹은 100번에서 직접 이동) 값과 비교하여 더 작은 값을 선택해 모든 반복이 끝날 때 최솟값을 얻을 수 있도록 한다.

코드

package java_baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class prob1107_2 {
    static int N;
    static int M;

    public static void main(String[] args) throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        boolean button[] = new boolean[10];

        for (int i = 0; i < 10; i++) {
            button[i] = true;
        }
        for (int i = 0; i < M; i++) {
            button[sc.nextInt()] = false;
        }

        int ans = Math.abs(N - 100);

        for (int tmp = 0; tmp <= 999999; tmp++) {
            String str = String.valueOf(tmp);
            int len = str.length();

            boolean check = true;
            for (int j = 0; j < len; j++) {
                if (!button[str.charAt(j) - '0']) {
                    check = false;
                    break;
                }
            }
            if (check) {
                int min = Math.abs(N - tmp) + len;
                ans = Math.min(min, ans);
            }
        }
        System.out.println(ans);
    }
}

결과