1107

리모컨 (https://www.acmicpc.net/problem/1107)

 

숏코드를 통해 배우자 https://www.acmicpc.net/source/23063404

 

1. 중복순열의 값을 dfs의 res 인자를 통해 넘겨줌.

기존 방식 perm 배열 선언 후, 별도 배열에 저장했으나 이번 경우, 매번 perm에서 int를 생성하는 부분이 비효율적임.

 

2. dfs에서 중복순열을 계산하기 전 answer의 초기값으로 100-N을 미리저장.

기존제출 방식에서 사용한 min, minDiff를 따로 저장하여 계산할 필요가 없어짐.

 

위 두가지 개선만으로 코드량이 줄고, 이해하기가 훨씬 쉬워짐.

 

 

중복순열

//https://www.acmicpc.net/source/23063404

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

public class Main {

	static int N, M;
	static int[] arr;
	static int[] ch;
	static int CURRENT_CH = 100;
	static boolean DBG = false;
	static String in;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		in = br.readLine();
		N = Integer.parseInt(in);
		M = Integer.parseInt(br.readLine());
		arr = new int[10];
		if (M != 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < M; i++) {
				arr[Integer.parseInt(st.nextToken())] = 1;
			}
		}
		ch = new int[10];

		answer = Math.abs(CURRENT_CH - N);
		dfs(0, 0, arr);
		System.out.println(answer);

	}

	static int answer;

	private static void dfs(int level, int res, int[] arr) {

		if (level >= 1)
			answer = Math.min(level + Math.abs(res - N), answer);

		if (level == in.length() + 1) {
			return;
		}

		for (int i = 0; i < 10; ++i) {
			if (arr[i] == 0) {
				dfs(level + 1, res * 10 + i, arr);
			}
		}
	}

}

 

 

 

기존제출

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

public class Main {

	static int N, M;
	static int[] arr;
	static int[] ch;
	static int CURRENT_CH = 100;
	static boolean DBG = false;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String in = br.readLine();
		N = Integer.parseInt(in);
		M = Integer.parseInt(br.readLine());
		arr = new int[10];
		if (M != 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < M; i++) {
				arr[Integer.parseInt(st.nextToken())] = 1;
			}
		}
		ch = new int[10];
		int[] perm = new int[in.length() + 1];

		if (N == CURRENT_CH) {
			System.out.println(0);
			return;
		}
		if (DBG) {
			for (int i = 0; i < 10; ++i) {
				System.out.printf("%d %d\n", i, arr[i]);
			}
		}

		dfs(0, perm, arr);
		int cnt = 0;
		if (DBG) {
			System.out.printf("min : %d min diff : %d N : %d\n", min, minDiff, N);
		}
		String tmp = min + "";
		int pressed = Math.abs(tmp.length() + minDiff);
		if (DBG) {
			System.out.printf("compare : %d, %d\n", pressed, Math.abs(N - CURRENT_CH));
		}
		cnt = Math.min(pressed, Math.abs(N - 100));
		System.out.println(cnt);

	}

	static int minDiff = Integer.MAX_VALUE;
	static int min = Integer.MAX_VALUE;
	static int minLevel = Integer.MAX_VALUE;

	private static void dfs(int level, int[] perm, int[] arr) {

		int tmp = 0;
		boolean isNoPerm = true;
		for (int i = 0; i < level; i++) {
			isNoPerm = false;
			if (DBG) {
				System.out.print(perm[i] + " ");
			}
			tmp = tmp * 10 + perm[i];
		}
		if (DBG) {
			System.out.println();
		}
		if (!isNoPerm) {
			if (Math.abs(N - tmp) < minDiff) {

				minDiff = Math.abs(N - tmp);
				if (DBG) {
					System.out.println("level : " + level + " min :" + tmp + " minDiff : " + minDiff);
				}
				min = tmp;
				minLevel = level;
			} else if (Math.abs(N - tmp) == minDiff) {

				if (minLevel > level) {
					minDiff = Math.abs(N - tmp);
					if (DBG) {
						System.out.println("level : " + level + " min :" + tmp + " minDiff : " + minDiff);
					}
					min = tmp;
					minLevel = level;
				}

			}
		}

		if (level == perm.length) {
			return;
		}

		for (int i = 0; i < 10; ++i) {
			if (arr[i] == 0) {
				perm[level] = i;
				dfs(level + 1, perm, arr);
			}
		}

	}

}

 

BF 방식

//https://www.acmicpc.net/source/8366388
import java.util.Scanner;

public class Main {
	static boolean[] btn;
	public static void main(String[] ar){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		btn = new boolean[10];
		for(int i=0; i<k; i++) btn[sc.nextInt()]=true;
		
		int ans = Math.abs(100-n);
		for(int i=0; i<=1000000; i++){
			if(allBtn(i)){
				int temp = (i+"").length() + Math.abs(n-i);
				ans = Math.min(ans, temp);
			}
		}
		System.out.print(ans);
	}
	public static boolean allBtn(int ch){
		boolean ret = true;
		if(ch==0){
			if(btn[0]) ret = false;
		}else{
			while(ch>0){
				if(btn[ch%10]){
					ret = false;
					break;
				}
				ch /= 10;
			}
		}
		return ret;
	}
}