백준 1107번 리모컨 java

문제

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

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

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

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

입력

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

출력

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

 

 

 

백준알고리즘 기초-브루트포스에 있는 문제이다.

0~999,999 까지 모든 경우의 수를 살펴보아야 한다.

 

charAt(i)-'0' 또는 나머지연산(%)을 통해 고장여부를 확인한다.

 

ans를 갱신해가면서 최솟값을 찾는다.

 

주석으로 설명 대체.

 

 

 

import java.util.Scanner;

public class Exam1107_2 {

	static boolean[] broken = new boolean[10]; // 0~10

	static int possible(int c) {
		if (c == 0) { //0일때 예외처리
			if (broken[0]) {
				return 0;
			} else {
				return 1;
			}
		}
		int len = 0;
		while (c > 0) {
			if (broken[c % 10]) {
				return 0;
			}
			len += 1;
			c /= 10;
		}
		return len;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 이동 원하는 채널
		int m = sc.nextInt(); // 고자안 채널 갯수
		for (int i = 0; i < m; i++) {
			int x = sc.nextInt();
			broken[x] = true; // 트루면 고장!
		}

		int ans = Math.abs(n - 100);
		/*
		 * 초기 채널은 100이다. 모든 리모콘의 숫자버튼이 고장났을 경우 +-버튼으로만이동 가능하도록 초기값을 설정해준다.
		 */

		// 0부터 1000000까지 모든 채널을 돌면서 N으로 가장 적은 버튼을 눌러 이동할 수 있는 채널을 찾는다.
		for (int i = 0; i < 1000000; i++) {
			int c = i;
			int len = possible(c);
			// len 변수: c로 숫자버튼만을 이용해서 이동이 가능한지, 가능하다면 몇 번의 버튼을 누르는지 구하는 변수
			if (len > 0) {
				int press = Math.abs(c - n);
				// press: 숫자버튼으로 n에 최대한 인접하게 이동한후 +또는 -를 몇 번 눌러야 하는지 구하는 변수
				if (ans > len + press) {
					ans = len + press;
				}

			}

		}
		System.out.println(ans);
	}
}