이 문제에서는 주의해야 하는 점이 몇 개가 있다.
입력의 차이
일반적인 입력의 경우에는 목표 숫자, 고장 버튼 개수, 고장 버튼 숫자들로 주어진다.
하지만 고장 버튼 개수가 0개인 경우가 존재한다.
이 때는 고장 버튼 숫자들이 주어지지 않는다.
그렇기 때문에 2가지의 경우를 나누어 생각하지 않고 고장 버튼 숫자들의 입력을 받는다면
solution은 고장 버튼 숫자들의 입력을 무한히 기다린다.
물론 고장 버튼 숫자들을 한 번에 읽지 않고 개수만큼 하나씩 읽으면 무한 대기하지 않는다.
하지만 고장난 버튼이 없을 경우에는 추가 로직 없이 +-으로만 이동하는 경우와 목표 채널의
길이 비교만을 통해 answer를 계산할 수 있기 때문에 나누는 것이 좋다.
검사 숫자
핵심 알고리즘은 완전 탐색을 통해 특정 채널을 누르고 증감버튼을 통해 목표 채널로 가는
것이다. 이 때 완전 탐색의 범위를 정해야 하는데 우선 0부터 탐색할 수 있다.
채널이 무한하기 때문에 상한값이 없다고 생각할 수 있으나 목표 채널의 범위가 정해져
있기 때문에 탐색의 상한값도 정해져 있다. 목표 채널은 최대 500,000이다.
만약 1,000,000 이상이 되면 그 밑의 어떤 숫자를 통해 목표 채널로 가는 것보다
오래 걸린다. 그렇기 때문에 최대 999,999를 상한값으로 정해야 한다.
핵심 알고리즘은 다음과 같다.
각각의 입력 숫자들을 완전 탐색한다.
숫자를 번호판으로 누를 수 있는지 확인한다.
누를 수 있으면 누른 후 증감 버튼을 이용해 이동하는 거리를 구한다.
현재 구해진 최소 거리와 비교한다.
private static final boolean[] isBroken = new boolean[10];
private static void solution() throws IOException {
int goalNumber = Integer.parseInt(reader.readLine());
if (Integer.parseInt(reader.readLine()) == 0) {
result.append(Math.min(
Math.abs(100 - goalNumber),
String.valueOf(goalNumber).length()));
} else {
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
while (tokenizer.hasMoreTokens())
isBroken[Integer.parseInt(tokenizer.nextToken())] = true;
int count = Math.abs(100 - goalNumber);
for (int i = 0; i <= 999999; i++)
if (canClickButton(i))
count = Math.min(
count,
String.valueOf(i).length() + Math.abs(i - goalNumber));
result.append(count);
}
}
private static boolean canClickButton(int number) {
char[] digits = String.valueOf(number).toCharArray();
for (char digit : digits)
if (isBroken[Character.getNumericValue(digit)])
return false;
return true;
}