백준 15663: N과 M (9) (JAVA)

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

---

틀렸다. 모르겠다.

 

정답을 보기 전 했던 시도

1. HashSet<int[]>를 만들어, 중복된 수열은 포함하지 않도록 확인하는 방법 -> 일단 set.contains를 int[]에 대해 사용하니까 잘 안되더라. 그래서 관련하여 찾아봤는데, .contains는 두 object간에 equals를 수행하는 것이며, 그리고 '.equals()는 array에 대해서는 많은 사람들이 생각하는 대로 작동하지 않으니 쓰지말라'는 글을 찾았다(https://stackoverflow.com/questions/8777257/equals-vs-arrays-equals-in-java의 두 번째 답변.). 이후 위 링크의 첫 번째 답변처럼 Array.equals()을 사용하기 위해 HashSet에 대해 for문 돌려서 했더니 TLE.
2. 숫자를 String으로 합쳐 숫자로 나타내어 HashSet<Integer>에 넣는 방법 -> 10**25 > 2 * 64라 기각.
   1. 그런데 쓰다보니, Integer로 바꿀 필요가 없지 않을까? 그냥 String으로 넣어서 같은 값이 있는지 보면 안 되나...? 실제로 해보니까 됐다: 혼자 독백하다가 얻어걸렸다ㅋㅋ

 

풀이

1. 위의 혼잣말 2-1.대로 풀었다.
2. 인터넷에서 본 풀이: prevNum이라는 변수를 선언하여, 마지막에만 같은 원소가 들어가는게 아닌지 확인하면 된다는 풀이였다. 왠만한 코드는 보면 '음~그렇군~'하곤 하는데, 이건 '틀왜맞?' 소리가 나오더라. 그래서 손컴파일 해보니까 왜 되는지 알았다. prevNum은 combination마다 계속 0으로 초기화되기에, 마지막에서만 같은 원소를 넣는지 확인하게 된다. 즉, 4 2 \n 9 7 9 1이라는 예제를 생각해보면, 1을 뽑고 9가 들어가여 1 9라는 수열이 출력되었다면, prevNum에는 9가 저장되어 두번째 9는 if문에서 걸러지게 된다. 주저리주저리 적었는데, 손컴파일 해보면 바로 감이 온다!

 

코드

 

풀이1. HashSet<String>으로 중복 확인

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

public class Main {
	static int N, M;
	static int[] input;
	static boolean[] visited;
	static int[] nums;
	static StringBuilder sb = new StringBuilder();
	static HashSet<String> set = new HashSet<String>();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		input = new int[N];
		nums = new int[M];
		visited = new boolean[N];
		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(input);
		combination(0);
		System.out.println(sb);
	}
	
	public static void combination(int cnt) {
		if (cnt == M) {
			String str = "";
			for (int num: nums) {
				str += (num) + " ";
			}
			str += "\n";
			if (!set.contains(str)) {
				set.add(str);
				sb.append(str);
			}
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (visited[i]) continue;
			visited[i] = true;
			nums[cnt] = input[i];
			combination(cnt+1);
			visited[i] = false;
		}
	}
}

 

풀이2. prevNum으로 같은 값 제외

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

public class Main {
	static int N, M;
	static int[] input;
	static boolean[] visited;
	static int[] nums;
	static StringBuilder sb = new StringBuilder();
	static HashSet<Integer> set = new HashSet<Integer>();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		input = new int[N];
		nums = new int[M];
		visited = new boolean[N];
		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(input);
		combination(0);
		System.out.println(sb);
	}
	
	public static void combination(int cnt) {
		if (cnt == M) {
			for (int num: nums) {
				sb.append(num+" ");
			}
			sb.append("\n");
			return;
		}
		
		int prevNum = 0;
		for (int i = 0; i < N; i++) {
			if (visited[i] || input[i] == prevNum) continue;
			visited[i] = true;
			nums[cnt] = input[i];
			prevNum = input[i];
			combination(cnt+1);
			visited[i] = false;
		}
	}
}

 

퍼포먼스 비교

맨 위가 풀이 1, 맨 아래가 풀이 2이다. 당연히 풀이 1이 더 나은 성능을 보인다.