[백준][JAVA] BOJ 1107 리모컨

 

문제 읽기🤔

---

문제

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

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

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

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

 

1) 100번에서 +,-를 눌러 N으로 이동하는 경우 vs 숫자를 조합하여 만들어진 채널에서 +,-를 눌러 N으로 이동하는 경우

 

입력

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

 

2) 고장난 버튼(M)이 0이라면 셋째줄 입력은 주어지지 않는다!

 

출력

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

 

예제 입력 1 복사

5457
3
6 7 8

 

예제 출력 1 복사

6

 

 

문제 풀이📝

---

삽질의 연속...

https://blog.naver.com/occidere/221354997206

[백준] 1107 - 리모컨

 

치명적인 예외 하나를 빠트려서 코드를 갈아엎어야 했다.

나는 N의 자릿수만큼의 숫자를 뽑아서 그 차이가 최소인 값을 선택하는 방식으로 구현하였다.

그러나 아래의 반례에 처참히 무너지고 말았다.

1555
8
0 1 3 4 5 6 7 9

위의 블로그에서 제시한 반례이다.

내가 구현한 로직에 따르면

2, 2, 2, 2를 선택, N과의 차이는 667이 되므로 답은 667 + 4(숫자 버튼을 누른 횟수) = 671이 된다.

그러나 치명적인 함정이 있었다.

8, 8, 8을 선택할 경우 N과의 차이는 667이지만 숫자버튼을 누른 횟수는 3이므로 667 + 3 = 670이 된다.

 

진짜 이런 실수하면 안되는데...

코드를 짜기 전에 반드시 설계부터 하는 습관을 들여야겠다!!

 

위의 블로그를 참고하여 새로 짠 로직은 다음과 같다.

    static void find(String num) {
        for (String btn : buttons) {
            String temp = new StringBuilder(num).append(btn).toString();
            min = Math.min(min, Math.abs(n - Integer.parseInt(temp)) + temp.length());

            if (temp.length() < 6) {
                find(temp);
            }
        }
    }

앞자리수부터 고장나지 않은 숫자 버튼을 덧붙이면서 나올 수 있는 경우의 수들을 만들었다.

min은 버튼을 가장 적게 누른 횟수로, 경우의 수와 비교를 하면서 갱신해준다.

N은 최대 500,000이기 때문에 6자리를 넘어가게 되면 더 이상 재귀를 돌지 않게 해주었다.

 

 

구현🛠

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

    static final int MAX_BUTTONS = 10;
    static int n;
    static int broken;
    static Set<String> buttons;
    static int min;

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

        n = Integer.parseInt(br.readLine());
        broken = Integer.parseInt(br.readLine());
        buttons = new HashSet<>();
        min = Integer.MAX_VALUE;

        for (int i = 0; i < MAX_BUTTONS; i++){
            buttons.add(String.valueOf(i));
        }
        if (broken != 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < broken; i++){
                buttons.remove(st.nextToken());
            }
        }

        min = Math.min(min, Math.abs(100 - n));

        if (!buttons.isEmpty()) {
            find("");
        }

        System.out.println(min);
    }

    static void find(String num) {
        for (String btn : buttons) {
            String temp = new StringBuilder(num).append(btn).toString();
            min = Math.min(min, Math.abs(n - Integer.parseInt(temp)) + temp.length());

            if (temp.length() < 6) {
                find(temp);
            }
        }
    }
}

 

 

실행결과✅