백준 1107 리모컨

리모컨 : https://www.acmicpc.net/problem/1107

1107번: 리모컨

리모컨 일부 숫자가 고장났다 이때 멀쩡한 버튼과 +,-버튼만가지고 원하는 채널까지 갈때 최소 몇번 눌러야 하는지 구하는 문제 였다.

완탐을 통해 입력할수 있는 모든 숫자를 가지고 비교를 하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;

public class 리모컨 {
	public static String targetChannel;
	public static int N = 0, answer = Integer.MAX_VALUE;
	public static List<Integer> button = new ArrayList<Integer>();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		targetChannel = br.readLine();
		N = Integer.parseInt(br.readLine());
		if (N != 0) {
			st = new StringTokenizer(br.readLine());
		}
		for (int n = 0; n < N; n++) {
			button.add(Integer.parseInt(st.nextToken()));
		}
		dfs(0, new StringBuilder());
		answer = answer > Math.abs(Integer.parseInt(targetChannel) - 100)
				? Math.abs(Integer.parseInt(targetChannel) - 100)
				: answer;
		System.out.println(answer);
	}

	public static void dfs(int count, StringBuilder sb) {
		if (count > targetChannel.length()) {
			return;
		}

		for (int i = 0; i < 10; i++) {
			if (button.contains(i)) {
				continue;
			}
			sb.append(i);
			int result = sb.length() + Math.abs(Integer.parseInt(targetChannel) - Integer.parseInt(sb.toString()));
			answer = answer > result ? result : answer;
			dfs(count + 1, sb);
			sb.deleteCharAt(sb.length() - 1);
		}
	}
}

dfs의 종료 조건은 targetChannel보다 size가 클경우로 해주었다.

그 이유는

997

8

2 3 4 5 6 7 8 9

와 같은 케이스 였기 때문이다. 이경우 1000에서 3번 - 한것이 제일 빠르기 때문이다.

만약 count == targetChannel이라고 했다면 111에서 997까지 +로 올라가야 하기 때문에 비효율 적이다.

또한

answer = answer > Math.abs(Integer.parseInt(targetChannel) - 100)
				? Math.abs(Integer.parseInt(targetChannel) - 100)
				: answer;

해당 조건을 넣어주어 +,-로 이동이 더 빠른 경우를 해결해 주었다.

마지막으로 고장난 버튼이 없는경우도 있기때문에 StringTokenizer를 고장난 버튼이 있는경우에만 생성해주어야한다

그렇지 않으면 85%쯤에서 런타임애러(NullPointer)를 겪게 된다 ㅠㅠ

if (N != 0) {
			st = new StringTokenizer(br.readLine());
}

이번 문제는 다양한 조건을 생각 해야 했기 때문에 굉장히 좋은 문제 였던것 같다.