1107 리모컨 [JAVA]

문제 분석

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

티비의 채널을 N으로 변경하려하는데

M개의 숫자 버튼이 고장나있다.

그리고, +,- 버튼이 존재한다.

100번에서 N번 채널으로 최소한의 버튼 조작으로 이동할 때 그 이동 횟수를 구하는게 문제다.

 

처음에 앞의 자리수 부터 가장 가까운 수를 넣어 최적의 이동 횟수를 구하는 방법을 생각해봤었는데

생각해보면 10000이라는 숫자에 대해서 1에 가장 가까운 유효한 수는 2지만 9999가 더 가깝다.

 

그런데, 주어진 N의 범위가 500000 밖에 되지 않는다.

즉, 10^6가지의 숫자만 고려해주면 되고 이정도는 충분히 돌아도 제한 시간을 만족하게 된다.

 

따라서 나는 아래와 같은 구조로 문제를 풀었다.

 

주어진 숫자의 길이 -1 의 숫자 중 가장 큰 수 (여기서, 숫자의 길이가 1이라면 숫자의 길이 -1은 해당되지 않으니 빼준다.)

주어진 숫자의 길이에 해당하는 모든 경우의 수

주어진 숫자의 길이 +1의 숫자 중 가장 작은 수

시작 채널인 100

 

이렇게 구성된 수들의 집합에 대해서

N번의 채널로 이동하는 데 필요한 이동 횟수를 PQ에 넣어 힙소트를 시킨다면

결국에 PQ의 peek엔 최소 이동 횟수가 들어 있게 된다.

 

코드

import java.util.*;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Set<Integer> availableSet =new HashSet<>();
        for (int i = 0; i < 10; i++) {
            availableSet.add(i);
        }
        for (int i = 0; i < m; i++) {
            int broken = sc.nextInt();
            availableSet.remove(broken);
        }
        String target = String.valueOf(n);
        int size = target.length();
        if(size == 1){
            if(availableSet.isEmpty()) {
                System.out.println(Math.abs(100-n));
                return;
            }
            int minFirst = Integer.MAX_VALUE;

            for (Integer i : availableSet) {
                minFirst = Math.min(minFirst, Math.abs(n-i) + 1);
                for (Integer integer : availableSet) {
                    int nextNum = i*10 + integer;
                    minFirst = Math.min(minFirst, Math.abs(n-nextNum) + 2);
                }
            }



            System.out.println(Math.abs(minFirst));
            return;
        }

        Set<Integer> shortDigitSet = new HashSet<>(availableSet);
        int maxShort = -1;
        for (Integer i : availableSet) {
            maxShort = Math.max(maxShort, i);
        }

        for (int i = 1; i < size - 1; i++) {
            Set<Integer> nextDigitSet = new HashSet<>();
            for (Integer integer : shortDigitSet) {
                for (Integer num : availableSet) {
                    int nextNum = integer*10 + num;
                    maxShort = Math.max(maxShort, nextNum);
                    nextDigitSet.add(nextNum);
                }
            }
            shortDigitSet = new HashSet<>(nextDigitSet);
        }

        PriorityQueue<Integer> channelPQ = new PriorityQueue<>();
        if(maxShort!= -1)
            channelPQ.add(size-1+Math.abs(n-maxShort));
        channelPQ.add(Math.abs(n-100));


        Set<Integer> biggerDigitSet = new HashSet<>();

        for (Integer i : shortDigitSet) {
            for (Integer next : availableSet) {
                int nextNum = i*10 + next;
                channelPQ.add(Math.abs(nextNum-n) + size);
                if(size<6 && nextNum >= Math.pow(10,size-1))
                    biggerDigitSet.add(nextNum);
            }
        }


        int minBiggerDigit = Integer.MAX_VALUE;
        for (Integer i : biggerDigitSet) {
            for (Integer next : availableSet) {
                int nextNum = i*10 + next;
                minBiggerDigit = Math.min(minBiggerDigit, nextNum);
            }
        }
        channelPQ.add(Math.abs(minBiggerDigit-n) + size+1);

        Integer poll = channelPQ.poll();
        System.out.println(poll);


    }

}