[BOJ] 1107 - 리모컨 JAVA

www.acmicpc.net/problem/1107

1107번: 리모컨

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

예제 입력 1

5457

3

6 7 8

예제 출력 1

6

예제 입력 2

100

5

0 1 2 3 4

예제 출력 2

0

예제 입력 3

500000

8

0 2 3 4 6 7 8 9

예제 출력 3 복사

11117

 

 

 

 

 

 

 

풀이 .

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int n = Integer.parseInt(br.readLine());  // 목표 채널
        int m = Integer.parseInt(br.readLine());  // 망가진 버튼 수
        boolean[] isBroken = new boolean[10];  // 버튼 고장 여부

        if(m != 0) {
            st = new StringTokenizer(br.readLine());
        }
        for(int i = 0; i < m; i++) {
            int brokenBtn = Integer.parseInt(st.nextToken());
            isBroken[brokenBtn] = true;
        }

        if(n == 100) {  // 예외처리
            System.out.println(0);
            return;
        }

        int ans = Math.abs(n - 100);  // 초기값은 숫자 없이 + or - 이동
        for(int i = 0; i <= 1000000; i++) {  // i까지 숫자버튼으로 이동 후 +,- 버튼으로 이동하는 수
            String strChan = String.valueOf(i);

            // 숫자 버튼으로 이동 가능한지 체크
            boolean isPossible = true;
            for(int j = 0; j < strChan.length(); j++) {
                int btn = strChan.charAt(j) - '0';
                if(isBroken[btn]) {
                    isPossible = false;
                    break;  // 고장난 버튼이 있으면 다이렉트로 접근 불가능
                }
            }

            if(isPossible) {
                int cnt = strChan.length() + Math.abs(i - n);  // 숫자 이동 후 +,- 이동
                ans = Math.min(ans, cnt);
            }
        }
        System.out.println(ans);
    }
}

 

예외처리 때문에 한참을 해맸다.

M의 최소값이 0인데 M이 0일 때도 고장난 버튼에 대한 입력을 받으려고 해서 NullPointer 에러가 발생했었다.

 

초기값은 100에서 + or - 만을 사용해서 갈 수 있는 횟수로 둔다.

 

그 후 1~1,000,000에 대해 숫자버튼 이동 후 + or - 로 이동한 수를 모두 구해가며 최소값을 찾는다. (이 부분이 브루트 포스)

 

백만까지 검사하는 이유? 

-> N의 최대값 50만에 대해서 1~50만, 100만~50만 양 방향을 모두 고려해야 함