[백준 - 1107번] 리모컨 - Java //Wello Horld//

이번에는 백준 알고리즘의 1107번 문제 "리모컨"을 풀어보도록 하자

문제가 살짝 복잡한데, 수빈친구가 가지고 있는 리모컨의 일부 숫자 버튼이 고장났다. 수빈이가 현재 보고 있는 채널은 100번이고, 입력으로 수빈이가 이동하려고 하는 채널 N, 고장난 버튼의 개수 M, 그리고 고장난 버튼이 있는 경우에 셋째줄에 고장난 버튼이 주어지고, 출력으로 채널 N 으로 이동하기 위해 버튼을 최소 몇번 눌러야 하는지를 출력하는 문제인데, 입력으로 주어지는 채널이 500,000이므로 반복문으로 여러번 판별해주다 보면 시간초과가 뜰 위험이 있다. 이것을 주의하면서 문제를 풀면 된다.

일단 부르트포스(완전탐색)으로 문제를 풀었다. 총 이동가능한 채널의 개수는 입력의 상한이 500,000 이었으므로, 1,000,000(백만)으로 잡았고(이것보다는 작을 것으로 생각된다), 각각의 채널에 대해 이동가능한지 판별했다.

일단, 입력을 다 받아온 다음에, 답을 집어넣을 ans를 정수형으로 지정하고, Math.abs(N - 100) 으로 초기화 시켜줬다. 그이후에, 0부터 1,000,000 까지 반복문을 통해 채널의 가능여부를 판별했는데, 정수형태 각 자리의 값을 얻기위해 

while (chTemp > 0) {
    if(brk[chTemp % 10]){
        length = 0;
        break;
    }
    length++;
    chTemp = chTemp / 10;
}

위와 같이, 코드를 작성했다. 일단, chTemp의 값은 반복문으로 받아오는 채널이고, 그 채널이 0보다 크면 채널로 이동이 가능한지 판별하는 코드이다. 그리고, length는 해당 채널로 이동하기 위해 리모콘으로 버튼을 누르는 횟수를 나타낸다. 이렇게 chTemp를 반복문으로 각 자리의 값이 리모콘에 고장난 부분과 일치한지 판단해서 고장난 부분과 일치하면 length를 0으로 만들어주고 반복문을 멈추고, 그렇지 않으면 length를 1씩 더해준다.

이렇게 해서, length가 0보다크면 Math.min(ans, length + Math.abs(channel - N)) 으로 최소값을 구해준다. 이 부분에 대해 설명을 해보자면, (channel - N) 을 통해, 채널 번호와 입력으로 받은 값을 빼주어서 얼마만큼 차이가 나는지 구하고 절대값을 씌워준 다음에 채널의 길이를 더해주어서 해당 채널로 이동하기위한 값을 구할 수 있다.

성공한 코드 전문은 아래와 같다.

import java.io.*;
import java.util.*;

public class sample3 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Integer N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        boolean chkZero = false;
        boolean[] brk = new boolean[10];
        if(M > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                int chk = Integer.parseInt(st.nextToken());
                if(chk == 0) chkZero = true;
                brk[chk] = true;
            }
        }
        int ans = Math.abs(N - 100);
		for (int i=0; i<=1000000; i++) {
            int channel = i, chTemp = i;
            int length = 0;
            if(i == 0){
                if(chkZero) length = 0;
                else length = 1;
            } 
            while (chTemp > 0) {
                if(brk[chTemp % 10]){
                    length = 0;
                    break;
                }
                length++;
                chTemp = chTemp / 10;
            }
			if (length > 0) {
                ans = Math.min(ans, length + Math.abs(channel - N));
			}
        }
        bw.write(ans + "\n");
        bw.flush();
        br.close();
        bw.close();
    }
}

 

1107번: 리모컨

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