BOJ) 리모컨

리모컨

1107번: 리모컨

풀이

 

리모콘이 고장나면 고치거나 바꿔야하는데, 그대로 써서 골치아프게한 문제다.

우선, 1~9 버튼과 채널 위아래 이동 + - 버튼 11개가 있는 리모컨이다.

그리고, 입력에서 버튼이 고장난 갯수와 버튼의 위치를 알려주는데, 여기서 런타임에러가 한번 떴다.

 

처음에는 if(n !=ZERO)를 해주지 않아서, n이 0인 경우 ( 고장난 버튼이 없는 경우 ) 에 입력을 받고 저장하려고 시도해서 에러가 났다.

그래서 if문을 통해 걸러줬다.

 

이 문제는 어제 짧은 시간동안 너무 많은 문제를 풀면서, 잘 풀리지 않았던 문제였다.

그래서 다른 분들의 풀이를 살펴봤는데, 리모컨 숫자 버튼으로 이동할 수 있는 모든 채널에서 위아래 버튼을 통해 원하는 채널 번호까지 가는 경우의 수를 모두 탐색하는 것이었다.

시간초과가 안나나? 생각했는데, 아주 무리없게 돌아갔다.

이렇게 완전탐색이 효율이 괜찮은 경우도 있구나 싶었다.

 

아무튼 로직은 이렇다.

 

0~9999999 번 까지 숫자 버튼을 통해 이동할 수 있는 채널은 이동한다. (숫자 버튼이 고장난 채널은 이동하지 않는다.)

해당 채널로 이동하면서 든 횟수를 가져온다. (999번이면 3번의 버튼 클릭)

그리고 해당 번호에서 틀고 싶은 채널의 번호로 위아래(+ -) 이동이 몇 번 필요한지 더해준다.

 

위의 버튼 클릭 수의 최솟값을 최신화하면서 답을 찾아 나갔다.

생각보다 간단하지만, 알고리즘 문제를 풀면서 경우의 수가 많은데, 이런 전체 탐색은 하지 않는 쪽이 좋다고 생각해서 그런지 어색하다.

이런 경우도 있다는 것을 유의해야겠다.

 

 

코드

 

 

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

public class Main {
    final static int MAX = 9, MAX_CHANEL=999999, ZERO =0, BASIC = 100;
    static boolean[] brokenBtn;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int chanel = Integer.parseInt(br.readLine());
        brokenBtn = new boolean[MAX+1];
        int n = Integer.parseInt(br.readLine());
        if(n !=ZERO) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int i = ZERO; i < n; i++) {
                brokenBtn[Integer.parseInt(st.nextToken())] = true;
            }
        }
        br.close();

        solution(chanel);
    }

    private static void solution(int chanel) {
        int answer = Math.abs(BASIC-chanel);

        for(int i=ZERO; i<=MAX_CHANEL; i++) {
            int clickBtn = getClick(i);
            if(clickBtn >ZERO) {
                int upDown = Math.abs(i-chanel);
                answer = Math.min(answer, clickBtn+upDown);
            }
        }
        System.out.println(answer);
    }

    private static int getClick(int num) {
        int result =ZERO;
        if(num ==ZERO) {
            if(!brokenBtn[ZERO]) { result =1; }
        } else {
            while(num >ZERO) {
                if(brokenBtn[num%10]) {
                    result =ZERO;
                    break;
                }
                result++;
                num/=10;
            }
        }
        return result;
    }
}