문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
예제 입력 1
5457
3
6 7 8예제 출력 1
6예제 입력 2
100
5
0 1 2 3 4예제 출력 2
0예제 입력 3
500000
8
0 2 3 4 6 7 8 9예제 출력 3
11117예제 입력 4
100
3
1 0 5예제 출력 4
0예제 입력 5
14124
0예제 출력 5
5예제 입력 6
1
9
1 2 3 4 5 6 7 8 9예제 출력 6
2예제 입력 7
80000
2
8 9예제 출력 7
2228문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static boolean[] numbers=new boolean[10];
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(br.readLine());
int M=Integer.parseInt(br.readLine());
int comp=Integer.MAX_VALUE;
if(M!=0){
StringTokenizer st=new StringTokenizer(br.readLine());
for(int i=0;i<M;i++){
int num=Integer.parseInt(st.nextToken());
numbers[num]=true;
}
for(int t=0;t<=999999;t++){
String tmp=String.valueOf(t);
boolean flag=false;
for(int i=0;i<tmp.length();i++){
if(numbers[tmp.charAt(i)-'0']){
flag=true;
break;
}
}
if(flag) continue;
comp=Math.min(comp,Math.abs(t-N)+tmp.length());
}
comp=Math.min(Math.abs(100-N),comp);
}else{
comp=Math.min(Math.abs(100-N),String.valueOf(N).length());
}
System.out.println(comp);
}
}처음에는 이동하려는 채널 N을 문자열로 만들어 한 자리씩 비교하여 고장난 숫자가 있다면 그 숫자를 기준으로 작거나 큰 숫자들을 확인하여 사용할 수 있는 번호인지 판단하려고 했다.
그렇게 해버리면 예시문제가 계속 틀리게 된다.
예시
80000
2
8 9위의 예시를 보면 8을 사용하지 못하고 0은 사용이 가능하기 때문에 원래 짜려고 했던 코드를 이용하면 70000을 이용하여 최소값을 정한다.
하지만 77777로 이동한 뒤 +로 이동하면 70000을 이용했을 때보다 최소값이 나오게 된다. 이를 해결하기 위해 반복문을 추가하여 위 아래로 완전탐색을 하려고 했는데 결국 그 방법은 처음부터 500000까지 완전탐색을 하는 것과 같은 방식이라 노선을 틀어 0부터 완전탐색 하는 방법으로 구현했다.
채널 0번에서 500,000번까지 탐색해야하는데 만약 0번부터 8번까지 모든 숫자가 고장나면 999,999까지 간 뒤에 -로 이동해야하기 때문에 999,999번까지 완전탐색을 수행한다.
고장난 번호가 있는 경우에는 boolean 배열을 이용하고 true로 체크해준다.
해당 숫자에 고장난 번호가 있는 경우에는 다음 번호로 넘겨서 확인한다.
그러고 나온 번호와 타겟 번호와의 차이(+ 이용)와 해당 숫자의 길이(숫자 버튼 이용)를 더한 값의 최소값을 저장해준다.
그리고 숫자 버튼을 이용해서 이동한 것 보다 +, - 버튼만 이용하여 이동했을 때 더 적게 이동할 수도 있기 때문에 그 경우도 Math.min을 이용하여 최소값을 저장해준다.
그렇게 코드를 다 짜고 제출했는데 계속 틀렸다는 문구가 떴다.
여러 반례들을 모두 체크했을 때 모두 답이 맞았는데도 틀렸다는 문구가 떠서 답답한 상황에서 답이 틀린 경우를 찾게 됐다.
예시
1
10
0 1 2 3 4 5 6 7 8 9
99위의 경우에서 Integer.MAX_VALUE 값이 그대로 출력되는 것을 확인했다.
틀린 코드
for(int t=0;t<=999999;t++){
String tmp=String.valueOf(t);
boolean flag=false;
for(int i=0;i<tmp.length();i++){
if(numbers[tmp.charAt(i)-'0']){
flag=true;
break;
}
}
if(flag) continue;
comp=Math.min(comp,Math.abs(t-N)+tmp.length());
comp=Math.min(Math.abs(100-N),comp);
}이전에 틀렸던 코드의 일부분인데 위의 예시를 보면 0~9번 모두 고장이 났기 때문에 100번에서 이동할 수 밖에 없는데 flag 조건문에 걸려 이후에 있는 Math.min 연산을 하지 않게 된다.
즉, Math.min(Math.abs(100-N),comp); 코드를 for문 밖에 빼주어야했다.
완전탐색을 이용하면 풀 수 있는 문제였는데 코드를 하나하나 체크하지 않아 시간이 오래 걸렸다.
