[ 백준 / 1107 ] 리모컨 ( 자바 )

www.acmicpc.net/problem/1107

1107번: 리모컨

 

 

여러가지 경우의 수를 고려해야 한다.

 

* 방법1

v1.

내가 고려했던 것은, 100에서 +,-를 이용해서 이동하기

자릿수에 따라서 모든 경우의 숫자를 만들고 +,-를 이용해서 이동하기

 

v2.

+ 0을 누르고 이동하기

+ 자릿수가 하나 적을 때

+ 자릿수가 하나 많을 때

 

================================================================

* 방법2

 

v3.

1~10000까지 하나씩 확인하면서 검사하기

 

브루트포스를 통해서 만드는 작업인데, 많은 경우의 수를 고려했어야 했다. 특히 100에서 이동은 고려했지만, v2처럼 0을 누르고 이동하는 경우는 생각하지 못했다. 또한 무조건 자릿수가 같은 경우에 최소 이동을 할 것이라는 보장이 없다. 9의 경우 10에서 1을 빼는 경우가 5에서 9로 가는경우보다 짧은 거리를 이동할 것이다. 이런 경우를 고려해서 자릿수가 하나 적을 때와 하나 많을 때를 포함하여서 계산한다.

 

v3의 경우 훨씬 예외사항에 대한 고려가 적어진다. 하지만 중요한 것은 해당 숫자가 고장난 리모콘 번호를 어떻게 검사할 것인가? while문에서 계속 %10을 통해 일의자리 숫자를 하나씩 검사하도록 한다.

 

시간복잡도, 공간복잡도 모두 방법2 훨씬 좋다.

 

방법1

import java.util.*;
public class Main {
	
	static int answer=0;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int val = sc.nextInt();
		
		int N = sc.nextInt();
		int[] array = new int[10];
		for(int i=0;i<N;i++) {
			array[sc.nextInt()] = 1;
		}
		
		answer = Math.abs(val-100);
		if(array[0]==0) {
			int res = val+1;
			if(res<answer) answer = res;
		}
		
		int length = Integer.toString(val).length();
		recursive(val, "", array, length, 0);	
		System.out.println(answer);
	}
	
	public static void recursive(int val, String num, int[] array, int length, int nowLength) {
		if(num.startsWith("0")) return;
		
		if((nowLength == length-1 || nowLength == length || nowLength == length+1) && num!="" ) {
			int result = Math.abs(Integer.parseInt(num)-val)+nowLength;
			if(result<answer) {
				answer=result;
			}
			if(nowLength==length+1) return;
		}
		
		for(int i=0;i<array.length;i++) {
			if(array[i]==1) continue;
			recursive(val, num+i,array,length,nowLength+1);
		}
	}

}

 

 

 

방법2

import java.util.*;
public class Main {

	static int result;
	static int N;
	static int[] array;
	static int answer=0;
	static List<Integer> list = new ArrayList<>();
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		result = sc.nextInt();
		N = sc.nextInt();
		array = new int[10];
		for(int i=0;i<N;i++) {
			array[sc.nextInt()]=1;
		}
		
		//숫자를 제외한 나머지 숫자들에 대해서 list에 추가
		for(int i=0;i<=9;i++) {
			if(array[i]==0) list.add(i);
		}
		
		//100번에서 가까우면 바로 계산
		answer = Math.abs(result-100);
		
		//0이 기능하면 0에서 계산
		if(array[0]!=1) {
			answer = Math.min(answer, result+1);
		}
		
		for(int i=1;i<=1000000;i++) {
			if(isContain(i)) continue;
			
			int val = Integer.toString(i).length()+Math.abs(i-result);
			if(val<answer) answer = val;
		}
		
		System.out.println(answer);
	}
	
	public static boolean isContain(int N) {
		while(N!=0) {
			if(!list.contains(N%10)) return true; //포함하고 있으면 true 반환
			N = N/10;
		}
		
		return false;
	}
	
	

}