1107번 - 리모콘

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static StringBuilder str = new StringBuilder();
	static HashSet<Integer> set;
	static int min;
	static int len;
	
	static void r_perm(int n, int R) {
		if(n == R) {
			return;
		}
		for(int i=0;i<10;i++) {
			if(set.contains(i)) {
				str.append(i);
				int tmp = Integer.parseInt(str.toString());
				if(Math.abs(tmp - N) < min) {
					min = Math.abs(tmp - N);
					if(tmp > 0) {
						len = (int)Math.log10(tmp)+1;
					} else {
						len = 1;
					}
				} else if(Math.abs(tmp - N) == min) {
					if(tmp > 0 && len > (int)Math.log10(tmp)+1) {
						len = (int)Math.log10(tmp)+1;
					} else if(tmp == 0) {
						len = 1;
					}
				}
				r_perm(n+1, R);
				str.deleteCharAt(n);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		int diff = 0, direct = 0;
		min = Integer.MAX_VALUE;
		len = 0;
		if(M > 0) {
			set = new HashSet<>();
			for(int i=0;i<10;i++) {
				set.add(i);
			}
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int i=0;i<M;i++) {
				set.remove(Integer.parseInt(st.nextToken()));
			}
			if(N > 0) {
				r_perm(0, (int)Math.log10(N)+2);
			} else {
				r_perm(0, 2);
			}
			int res = min + len;
			System.out.println(Math.min(Math.abs(N-100), res));
		} else {
			diff = Math.abs(N-100);
			if(N > 0) {
				direct = (int)Math.log10(N)+1;
			} else {
				direct = 1;
			}
			System.out.println(Math.min(diff, direct));
		}
		br.close();
	}
}

접근방법의 차이로 1위 코드와 6배정도 시간 차이가 있습니다.

기본적인 아이디어는 채널 번호가 최대 500000이므로 숫자 6개의 조합 (10π6 = 1000000)으로 중복순열을 돌려도 시간초과가 나지 않는다는 점을 이용하여 모든 조합에서 N까지의 +, -로 이동하는 이동 횟수를 구하고 여기에 해당 조합을 입력하는 입력 횟수를 더하는 것입니다.

 

그렇게 효율적인 설계는 아니지만 고장난 버튼이 없는 경우 바로 가는 것과 직접 입력하는 것만 비교하면 되기 때문에 if else문으로 버튼이 고장난 경우와 고장나지 않은 경우를 나누고 고장난 경우 set을 이용해 고장나지 않은 버튼만을 중복순열을 돌리고 문자열을 늘려나가는 방법으로 모든 조합에 대해 채널 입력 및 +,-로 버튼을 입력하는 횟수를 셉니다. 고장나지 않은 경우 바로 가는 것과 채널을 직접 입력하는 횟수를 비교해서 더 작은 쪽을 고릅니다.

 

여기서는 채널의 길이를 구하기 위해 log10을 사용했는데 문자열의 length()를 이용했다면 if else로 0인 경우를 생각해주지 않아도 되었을 것 같습니다.