[JAVA] 백준 1107 리모컨

 

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

문제분석

처음에는 사용 가능한 숫자를 가지고 모든 채널을 만들고, TreeSet을 활용해 N과 가장 가까운 정수를 찾아서 100과의 거리를 비교하면 되는 줄 알았다. 당연히 100과도 거리를 비교했다. 하지만 이 과정에서 자꾸 틀린 답이 나왔고, 이유를 보니 시간 초과가 메인일 것 같았다. 따라서 1~1_000_000 까지 모든 채널에 대하여"입력 가능 여부" 를 반환하도록 하였고, 브루트포스답게 딱 1M 개의 채널만 순회하니 정답을 찾을 수 있다.

 

 

 

코드

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

public class Main {
    static Set<Integer> broken = new HashSet<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        if (M > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) broken.add(Integer.parseInt(st.nextToken()));
        }

        int ans = Math.abs(N - 100); // +/-만 쓰는 경우

        // N 최대 500,000이라 보통 1,000,000까지 보면 충분합니다.
        for (int ch = 0; ch <= 1_000_000; ch++) {
            int len = typeLengthIfPossible(ch);
            if (len >= 0) {
                int press = len + Math.abs(ch - N);
                ans = Math.min(press, ans);
            }
        }

        System.out.println(ans);
    }

    // 입력 가능하면 "누른 숫자 버튼 개수" 반환, 불가능하면 -1
    static int typeLengthIfPossible(int x) {
        if (x == 0) {
            return broken.contains(0) ? -1 : 1;
        }
        int len = 0;
        while (x > 0) {
            int d = x % 10;
            if (broken.contains(d)) return -1;
            len++;
            x /= 10;
        }
        return len;
    }
}