[백준 *Java] - 리모컨 (1107)

 

리모컨 문제풀기

1107번: 리모컨

문제 설명
수빈이는 TV를 보고 있다.
수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다.
+를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고,
-를 누르면 -1된 채널로 이동한다.
채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다.
어떤 버튼이 고장 났는지 주어졌을 때,
채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는 지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고있는 채널은 100번이다.

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

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

 

👇 접근방식 (내생각 정리

1. 원하는 채널 N에 갈 수 있도록 가장 최소한의 방법은 고장나지 않은 수로 원하는 채널N 근처까지 갑니다.

• N 자릿수가 높은 순서대로 사용할 수 있는 숫자 리스트에서 찾습니다.
• 값이 있을 시, 앞 자리 값을 빈 변수에 문자열을 더해줍니다.
  • 숫자가 0일 시에, 사용할 수 있는 숫자 리스트에서 가장 큰 수와 가장 작은 수를 가지고 빈 변수에 담긴 수와 문자열 합을 한 뒤 숫자 대소 관계를 비교를 해야합니다(절대값). 그 후 차이가 더 나지 않은 수를 가지고 문자열을 더해줍니다.
• 값이 없을 시, 앞 자리 값을 가지고 +1, -1 -> +2, -2 .... 한 수를 가지고,  사용할 수 있는 숫자리스트에 있는 지 비교를 합니다.
  
  • 더해주고 또는 빼준 값이 사용 가능한 숫자 리스트에 만약 값이 있을 시? 해당 숫자를 빈 변수에 담습니다.
  • 0 일 시에는 0 -1 = 0이되어야합니다. '-1'이라는 건 없습니다
• 위의 방식을 계속 반복을 하여, 원하는 채널 N이라는 수에 최대한 가깝게 만드는 작업을 합니다.
• 그 이후에 두 수를 빼준 뒤, 절대값을 씌워서 위의 방식대로 했을 때 더해줍니다.
• 예외처리가 있어야합니다. 
  • 채널은 100 부터 시작합니다. 고로, 이 부분까지 비교를 해줘서 대소관계를 따져야합니다.
• 그러면, 최소한이 나올 거 같다는 생각입니다.

 

이제 어느정도 생각이 정리가 됐으니 코드로 구현을 해보겠습니다.

 

코드 구현 중에 예외처리를 해주어야할 부분이 계속 생겨나기 때문에 애초에 접근 자체를 잘못 한 거 같습니다..

실패 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.LinkedList;

public class Main {
    static String [] channel;
    static List<Integer> keypad = new LinkedList<>(Arrays.asList(0,1,2,3,4,5,6,7,8,9));

    public static int searchMax () {
        int max = Integer.MIN_VALUE;
        for (int l : keypad) {
            max = Math.max(l, max);
        }
        return max;
    }

    public static int searchMin () {
        int min = Integer.MAX_VALUE;
        for (int l : keypad) {
            if (l == -1) continue;
            min = Math.min(l, min);
        }
        return min;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        List<Integer> list = new ArrayList<>();
        String str = br.readLine();
        channel = str.split("");
        int N = Integer.parseInt(br.readLine());

        // 고장난 게 없을 시?
        if (N == 0) {
            System.out.println(str.length());
            return;
        }

        // 채널이 100일 경우에는 return 0을 해줍니다.
        if (str.equals("100")) {
            System.out.println("0");
            return;
        }

        // 1. 고장난 건 -1로 체크합니다.
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            keypad.set(Integer.parseInt(st.nextToken()), -1);
        }


        for (int i = 0; i < channel.length; i++) {
            // 존재
            int chan = Integer.parseInt(channel[i]);

            if (keypad.contains(chan)) {
                if ("0".equals(channel[i])) {
                    if (list.get(0) > Integer.parseInt(channel[0])) {
                        list.add(searchMin());
                    }else if (list.get(0) < Integer.parseInt(channel[0])){
                        list.add(searchMax());
                    }
                }else list.add(chan);

            // 미존재
            } else {
                // 클 시?
                if (list.isEmpty() || list.get(0) == Integer.parseInt(channel[0])) {
                    int minus = 0;
                    int plus = 0;
                    for (int j = 1; j < 9; j++) {
                        plus = chan + j;
                        minus = chan - j;
                        if (plus > 9) plus = 9;
                        if (minus < 0) minus = 0;

                        if (keypad.contains(plus)) {
                            list.add(plus);
                            break;
                        } else if (keypad.contains(minus)) {
                            list.add(minus);
                            break;
                        }
                    }
                }else if (list.get(0) > Integer.parseInt(channel[0])) {
                    list.add(searchMin());
                }else if (list.get(0) < Integer.parseInt(channel[0])){
                    list.add(searchMax());
                }
            }
        }
        for (int i : list) {
            sb.append(i);
        }
        int a = Math.abs(Integer.parseInt(String.valueOf(sb)) - Integer.parseInt(str));
        System.out.println(a + sb.length());

    }
}

 

아래는 다른 분 코드를 참고해서 만든 코드입니다

아래 구현한 코드에 주석을 달아 놓았습니다.

 

완전탐색으로 0부터 최대값까지 모든 번호를 다 누르고 +, - 로 이동한 뒤, 그 중 최소값을 선택하면 됩니다.

정리하면, 아래코드는

i 값이 이동할 채널의 번호를 의미하여, i를 숫자로 이동하는 과정에서

고장난 번호가 있다면, 확인해 볼 필요가 없기 때문에 다음 반복으로 넘겨줍니다.

고장난 번호가 없는 경우에는 i 채널로 이동할 때, 누른 횟수인 len값과 +, -를 눌러 이동하게 될 잔여 횟수를 더해 비교합니다.

성공한 코드입니다.

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

public class Boj_1107 {
    static boolean[] broken = new boolean[10];

    private static int check (int i) {
        int len = 0;

        if(i == 0) { 
            if(broken[0]) len = 0; // 채널 0 예외 잡아줍니다.
            else len = 1;

            return len;
        }

        while(i > 0){
            // 고장났을 땐 return 0 즉, 채널이동 X
            if(broken[i % 10]){
                len = 0;
                return len;
            }
            len++;
            i /= 10;
        }
        return len;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int channel = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        // 고장났니, true
        for(int i = 0; i < N; i++){
            int num = Integer.parseInt(st.nextToken());
            broken[num] = true;
        }

        // 초기 채널은 100번이므로 +와 -번으로만 이동 가능한 것이 최대 이동 횟수이다.
        // 초기값 세팅을 해줍니다.
        int ans = Math.abs(channel - 100);

        // 입력될 수 있는 채널의 최댓값이 50만에서, 숫자(0~9)로 누를 수 있는 최대값은 999,999 까지 반복을 진행합니다.
        // 0부터 1000000 까지 모든 채널을 돌면서 N으로 가장 적은 버튼을 눌러 이동할 수 있는 채널을 찾는다.
        for(int i = 0; i < 1000000; i++) {
            int len = check(i);

            if(len != 0){
                // cnt는 숫자만 눌러서 근접한 숫자에서 몇번의 +나 -를 눌러야 하는지 나타낸다.
                int cnt = Math.abs(i - channel);
                if(ans > len + cnt) ans = len + cnt;
            }
        }
        System.out.println(ans);
    }
}