[코딩테스트/백준 알고리즘] 1107번 : 리모컨 (자바, Java 풀이)

문제

https://www.acmicpc.net/problem/1107

1107번: 리모컨

---

문제 설명

---

문제 풀이

입력값이 100인 경우

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();	//이동하려는 채널
        int channel = 100;	//현재 채널
        int result = Math.abs(N - channel);	//버튼을 누른 최소 횟수
        
        /*N이 100일 때*/
        if(result == 0) {
            System.out.println(result);
            System.exit(0);
        }
        else {
            /*코드*/
        }
        System.out.println(result);
    }
}

 버튼을 누른 최소 횟수를 저장하는 result값을 | N - channel |의 값으로 초기화한다. 이것은 현재 채널(100)에서 목표 채널까지 + 혹은 -만을 눌러서 이동한 횟수와 같다.

 만약 result 값이 0이라면 이미 100번 채널로 이동한 것이기 때문에 result값을 출력하고 종료한다.

그 외

 i를 0부터 1,000,000까지 증가시키면서 i가 숫자 버튼을 눌러서 만들 수 있는 수인지 확인한다. 만약 i가 숫자 버튼을 눌러서 만들 수 있는 수라면 N까지 '+' 혹은 '-'를 몇 번 눌러야 하는지 계산한다.

 i가 숫자버튼을 눌러서 만들 수 있는 수인지 검증하는 방법은 간단하다.

1. 나누기 연산을 통해 1의 자릿수, 10의 자릿수, 100의 자릿수 ... 등 각 자릿수로 분리한 뒤 broke[자릿수]의 값 확인
2. 문자열로 변환하여 각 자릿수로 분리한 뒤 broke[자릿수]의 값 확인 

나는 후자의 방식을 사용했다.

 

코드에서 i를 왜 1,000,000까지 증가시켜야 하는지 궁금할 수도 있어서 예시를 하나 들도록 하겠다.

Ex) 7만 쓸 수 있을 때 500,000을 만드는 방법

• 77,777을 만든 뒤, '+'를 422,223번 -> 422,228번
• 777,777을 만든 뒤, '-'를 277,777번 -> 277,783번

i가 500,000보다 더 클 때 버튼을 누르는 횟수가 더 적은 경우가 존재하기 때문이다.

---

코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();	//이동하려는 채널
        int channel = 100;	//현재 채널
        int result = Math.abs(N - channel);	//버튼을 누른 횟수
        int M = sc.nextInt();	//고장난 버튼의 수
        boolean[] broke = new boolean[10];	//버튼의 동작 여부

        /*고장난 버튼 확인*/
        for(int i = 0; i < M; i++) {
            broke[sc.nextInt()] = true;
        }
        
        /*N이 100일 때*/
        if(result == 0) {
            System.out.println(result);
            System.exit(0);
        }
        else {
            for(int i = 0; i <= 1000000; i++) {
                char[] num = Integer.toString(i).toCharArray();
                boolean make = true;	//채널을 만들 수 있는지 여부
                int count = 0;	//버튼 누른 횟수
                
                for (int j = 0; j < num.length; j++) {
                    if (!broke[(int)(num[j] - '0')]) {
                        count++;
                    }
                    else {
                        make = false;
                        break;
                    }
                }
                if (make) {
                    result = Math.min(result, Math.abs(N - i) + count);
                }
            }
        }
        System.out.println(result);
    }
}

---

총평

 브루트 포스 문제는 풀이를 처음 떠올렸을 때 '이걸 이렇게 하면 경우가 너무 많지 않은가? 다른 방법 없나?'라고 생각하게 되는 거 같다. 그래서 문제 풀이를 생각하고도 다른 방법이 없는지 생각하느라 문제 풀이에 시간이 오래 걸리는 경향이 있다. 지금은 공부하는 과정이니까 이런 생각을 하는 것도 좋은 거 같은데 나중에 코딩테스트에서는 처음 생각나는 풀이로 구현할 수 있도록 하는 것도 좋을 거 같다.