[BOJ 1107] 리모컨 (Java)

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.List;
import java.util.StringTokenizer;

public class Main{
	static int N;
	static int M;
	static int[] buttons= new int[10];
	static int move;
	static List<List<Integer>> li=new ArrayList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		String s=br.readLine();
		N=Integer.parseInt(s);
		M=Integer.parseInt(br.readLine());
		if (M>0) st=new StringTokenizer(br.readLine());
		for (int i=0; i<M; i++) {
			int num=Integer.parseInt(st.nextToken());
			buttons[num]=1; //고장난건 1
		}
		move=Math.abs(100-N);
		if (M==10) {
			System.out.println(move);
		}
		else {
			for (int i=1; i<=6; i++) {
				search(s,0, new char[i]);
			}
			System.out.println(move);
		}
	}
	
	private static void search(String s, int cnt, char[] num) {
		if (cnt==num.length) {
			int len=1;
			int make=Integer.parseInt(new String(num));
			while (true) {
				if (make%(int)Math.pow(10, len)==make && make/(int)Math.pow(10,len)==0) {
					break;
				}
				len++;
			}
			move=Math.min(move, len+Math.abs(N-make));
			return;
		}
		for (int i=0; i<10; i++) {
			if (buttons[i]==1) continue;
			num[cnt]=(char)(i+'0');
			search(s, cnt+1, num);
		}
	}
	

}

브루트 포스 알고리즘 문제로, 가능한 경우를 모두 해보는 문제이다.

처음 이와 같은 부분을 고려하지 못해서 AC를 받지 못했다.

-555번으로 가려고 한다면, 무조건 3자리 수만 후보군으로 고려한 것.

-3자리 수만 후보군으로 고려했다 하더라도, "005" 같은 케이스가 나올 경우를 고려하지 못한 것.

 

그래서 1자리부터~6자리(50만까지이므로) 경우의 수를 모두 따져보는 것으로 했다.

각 자리의 경우의 수를 따져보는 것은 재귀함수를 이용해, 고장나지 않은 가능한 번호를 순열 형태로 모두 뽑아주고, 자릿수를 구해 자릿수+abs(num-구한 수) 로 해서 Min 값을 정한다.

 

하지만 n자리 수를 구한다고 해놓고, n개를 뽑아놓고 "00032" 같은 case 를 위해서 자릿수를 계속 검사하는건 상당히 비효율적이다.

다른 분들의 코드를 보니, 아예 이렇게 순열로 구하는 형태가 아니라 0부터 100만까지 수를 모두 따져본 뒤,

각 수 중에 고장난 번호가 있는지 체크하고 고장난 번호가 없다면 자릿수+abs(num-구한수) 로 min을 갱신해주는 방식이다.

(https://seol-limit.tistory.com/48)

 

고장난 번호가 있는지 체크+자릿수 체크를 한번에 while 문을 이용해서 할 수 있다. 숫자를 10으로 나눈 나머지를 구해서 각 자릿수가 broken 되었는지 체크하고, 10으로 나눈 몫을 계속해서 같은 과정을  몫이 0이 될때까지 돌린다.