[Java] BOJ1107_리모컨

www.acmicpc.net/problem/1107

1107번: 리모컨

---

달리 빠르게 찾을 방법이 없기에 단순 브루트 포스 문제이다. 

가능한 숫자들을 순서에 상관 있게 누르고 같은 숫자를 또 누를 수 있기 때문에 중복순열로 구현하였다.

주의할 점은 찾아가야할 채널의 길이만큼만 누르는 것이 아니고 그보다 하나 짧은 길이, 하나 긴 길이를 다 체크해줘야 한다.

세 가지 체크를 하나의 함수로 구현할 방법도 있겠지만 나는 무식하게 각자 함수로 구현했다. 이래저래 조건 따지며 하나의 함수로 구현하는 것보다 조금씩만 바꿔서 여러 개의 함수로 놔두는 것이 구현 문제를 풀 때 시간을 더 아낄 수 있다.

이 문제 같은 경우도 기저 조건의 len만 바꿔주어 쉽게 구현할 수 있다.

 

다음 주의할 점은 '0'이다. 순열을 만들다 보면 0이 앞에 오는 경우가 있는데 이 경우에 0을 제거해줘야 한다.

하지만 여기서 0번 채널은 존재한다는 것을 잊으면 안 된다. 따라서 0 다음에 다른 숫자가 오는 채널에서 0을 제거해야 한다.

 

 

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N,len,M;
	static int[] rimo;
	static int res;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		len = s.length();
		N = Integer.parseInt(s);
		M = Integer.parseInt(br.readLine());
		if(M != 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int[] temp = new int[M];
			rimo = new int[10-M];
			for (int i = 0; i < M; i++) {
				temp[i] = Integer.parseInt(st.nextToken());
			}
			int index = 0;
			for (int i = 0; i < 10; i++) {
				boolean flag = false;
				for (int j = 0; j < M; j++) {
					if(temp[j] == i) {
						flag = true;
						break;
					}
				}
				if(!flag) {
					rimo[index++] = i;
				}
			}
		} else {
			rimo = new int[10];
			for (int i = 0; i < 10; i++) {
				rimo[i] = i;
			}
		}
		if(M == 10) {
			System.out.println(Math.abs(N-100));
			return;
		}
		
		res = Math.abs(N-100);
		permu1(0, new int[len]);
		if(len >= 2) permu2(0, new int[len-1]);
		permu3(0, new int[len+1]);
		System.out.println(res);
	}

	public static void permu1(int cnt, int[] result) {
		if(cnt == len) {
			String temp = "";
			boolean f = false;
			int zero = 0;
			for (int i = 0; i < cnt; i++) {
				temp += rimo[result[i]];
				if(!f) {
					if(rimo[result[i]] == 0) zero++;
					else f = true;
				}
			}
			if(!f) zero = 0;
			int n = Integer.parseInt(temp);
			n = Math.abs(n-N)+len-zero;
			res = Math.min(res, n);
			return;
		}
		for (int i = 0; i < 10-M; i++) {
			result[cnt] = i;
			permu1(cnt+1, result);
		}
	}
	public static void permu2(int cnt, int[] result) {
		if(cnt == len-1) {
			String temp = "";
			boolean f = false;
			int zero = 0;
			for (int i = 0; i < cnt; i++) {
				temp += rimo[result[i]];
				if(!f) {
					if(rimo[result[i]] == 0) zero++;
					else f = true;
				}
			}
			if(!f) zero = 0;
			int n = Integer.parseInt(temp);
			n = Math.abs(n-N)+len-1-zero;
			res = Math.min(res, n);
			return;
		}
		for (int i = 0; i < 10-M; i++) {
			result[cnt] = i;
			permu2(cnt+1, result);
		}
	}
	public static void permu3(int cnt, int[] result) {
		if(cnt == len+1) {
			String temp = "";
			boolean f = false;
			int zero = 0;
			for (int i = 0; i < cnt; i++) {
				temp += rimo[result[i]];
				if(!f) {
					if(rimo[result[i]] == 0) zero++;
					else f = true;
				}
			}
			if(!f) zero = 0;
			int n = Integer.parseInt(temp);
			n = Math.abs(n-N)+len+1-zero;
			res = Math.min(res, n);
			return;
		}
		for (int i = 0; i < 10-M; i++) {
			result[cnt] = i;
			permu3(cnt+1, result);
		}
	}
}

 

 

[참고]

www.acmicpc.net/board/view/46120

좋은 반례 모음집이 있다.