[백준] 1107 리모컨 - Brute Force / Java

• 문제 링크

1107번: 리모컨

 

• 풀이 과정

이동하려는 채널의 번호 n과 고장난 버튼을 m개 입력받는다.

이때 m = 0 일 경우, NullPointer 예외를 방지하기 위하여 m > 0 일 경우 버튼의 정보를 입력받는 조건을 건다.

 

먼저 모든 버튼이 고장났을 경우,

채널 100에서 +, - 버튼으로만 조작하는 횟수(Math.abs(n - 100)) 를 minCnt 의 초기값으로 둔다.

 

이어서 이동할 수 있는 채널의 모든 경우(0 ~ 999999) 를 완전 탐색한다.

현재 채널을 문자열화(String.valueOf(i))하여 해당 문자열의 모든 자릿수를 검사하며,

각각의 자릿수 중 하나라도 고장난 버튼과 일치하는 값이 존재한다면

isBroken = true 로 설정, 반복문을 빠져나온다.

 

만약 현재 채널을 고장난 버튼을 제외하고 조작하여 이동 가능(!isBroken) 하다면,

현재 채널에서 +, - 버튼으로만 조작하는 횟수(Math.abs(n - i)) 와

현재 채널을 숫자 버튼으로 조작한 횟수, 즉 현재 채널 문자열의 길이(press = channel.length()) 를 더하여

cnt 변수에 저장하고, minCnt 와 비교해 최소값을 갱신한다.

 

이러한 완전 탐색을 통해 구해진 버튼 조작 횟수의 최소값 minCnt를 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        boolean[] broken = new boolean[10];

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

        int minCnt = Math.abs(n - 100);

        for (int i = 0; i < 1000000; i++) {
            String channel = String.valueOf(i);
            int press = channel.length();

            boolean isBroken = false;
            for (int j = 0; j < press; j++) {
                if (broken[channel.charAt(j) - '0']) {
                    isBroken = true;
                    break;
                }
            }

            if (!isBroken) {
                int cnt = Math.abs(n - i) + press;
                minCnt = Math.min(minCnt, cnt);
            }
        }

        bw.write(minCnt + "\n");
        bw.flush();
    }

}