Baekjoon - 15663

문제

Solved.ac Class4

1차시도

public class Main {
	private static final StringBuilder sb = new StringBuilder();
	private static int size;
	private static int target;
	private static int[] newNum;
	private static boolean[] newIsVisit;
	private static int[] answers;
	private static Set<Integer> visitValue;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] input = br.readLine().split(" ");
		size = Integer.parseInt(input[0]);
		target = Integer.parseInt(input[1]);

		visitValue = new HashSet<>();

		int[] num = new int[size + 1];
		newNum = new int[size - 1];
		boolean[] isVisit = new boolean[size + 1];
		newIsVisit = new boolean[size - 1];
		answers = new int[target];
		input = br.readLine().split(" ");
		for (int i = 1; i < size + 1; i++) {
			num[i] = Integer.parseInt(input[i - 1]);
		}
		Arrays.sort(num);

		for (int i = 1; i < size + 1; i++) {
			answers[0] = num[i];
			isVisit[i] = true;
			makeNewArray(num, isVisit);
			solve(target, 1);
			isVisit[i] = false;
		}

		System.out.println(sb);
	}

	private static void makeNewArray(int[] num, boolean[] isVisit) {
		int count = 0;
		for (int i = 1; i < size + 1; i++) {
			if (!isVisit[i]) {
				newNum[count] = num[i];
				count++;
			}
		}
	}

	private static void solve(int target, int deep) {
		if (deep == target) {
			int check = check();
			if (!visitValue.contains(check)) {
				print();
				visitValue.add(check);
			}
			return;
		}

		for (int i = 0; i < size - 1; i++) {
			if (!newIsVisit[i]) {
				newIsVisit[i] = true;
				answers[deep] = newNum[i];
				solve(target, deep + 1);
				newIsVisit[i] = false;
			}
		}
	}

	private static int check() {
		int temp = 0;
		for (int i = 0; i < target; i++) {
			temp += (int)(answers[i] * Math.pow(10, target - (i + 1)));
		}
		return temp;
	}

	private static void print() {
		for (int i = 0; i < target; i++) {
			sb.append(answers[i]).append(" ");
		}
		sb.append("\n");
	}
}

오늘도 돌아온 DFS, Backtracking
하지만 문제가 생겼다.

실패

2차시도

위의경우, HashSet에 값을 저장해서 비교를 했다.
문제는
4 2
1 11 11 111
위와 같은 값이 들어가면
1, 111과
11, 11이
1111로 같은값으로 판정을 내리는 불상사가 일어난다. 따라서 이를 해결해야 했다.

public class Main {
	private static final StringBuilder sb = new StringBuilder();
	private static int size;
	private static int target;
	private static int[] newNum;
	private static boolean[] newIsVisit;
	private static int[] answers;
	private static Set<String> stringAnswers;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] input = br.readLine().split(" ");
		size = Integer.parseInt(input[0]);
		target = Integer.parseInt(input[1]);

		int[] num = new int[size + 1];
		newNum = new int[size - 1];
		boolean[] isVisit = new boolean[size + 1];
		newIsVisit = new boolean[size - 1];
		answers = new int[target];
		stringAnswers = new LinkedHashSet<>();
		input = br.readLine().split(" ");
		for (int i = 1; i < size + 1; i++) {
			num[i] = Integer.parseInt(input[i - 1]);
		}
		Arrays.sort(num);

		for (int i = 1; i < size + 1; i++) {
			answers[0] = num[i];
			isVisit[i] = true;
			makeNewArray(num, isVisit);
			solve(target, 1);
			isVisit[i] = false;
		}

		print();
	}

	private static void makeNewArray(int[] num, boolean[] isVisit) {
		int count = 0;
		for (int i = 1; i < size + 1; i++) {
			if (!isVisit[i]) {
				newNum[count] = num[i];
				count++;
			}
		}
	}

	private static void solve(int target, int deep) {
		if (deep == target) {
			convert();
			return;
		}

		for (int i = 0; i < size - 1; i++) {
			if (!newIsVisit[i]) {
				newIsVisit[i] = true;
				answers[deep] = newNum[i];
				solve(target, deep + 1);
				newIsVisit[i] = false;
			}
		}
	}

	private static void convert() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < target; i++) {
			sb.append(answers[i]).append(" ");
		}
		stringAnswers.add(sb.toString());
	}

	private static void print() {
		for (String answer : stringAnswers) {
			sb.append(answer).append("\n");
		}
		System.out.println(sb);
	}

}

그래서 LinkedHashSet에다가 저장했다.

성공