[ 백준 15665 JAVA ] N과 M(11) (Feat. 백트래킹)

https://www.acmicpc.net/problem/15665

15665번: N과 M (11)

 

 

review

계속 시간초과가 났던 문제.

public class Main {
	static int[] arr;
	static int N, M;
	static int[] result;
	static int setsize;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		
		result = new int[M];
		Set<Integer> set = new HashSet<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) set.add(Integer.parseInt(st.nextToken()));
		
		setsize = set.size();
		arr = new int[setsize];
		int idx =0;
		for(int a: set) arr[idx++] = a;
		
		Arrays.sort(arr);
		ncr(0);
	}
	public static void ncr(int idx) {
		if(idx == M) {
			for(int a : result) System.out.print(a+" ");
			System.out.println();
			return;
		}
		
		for(int i=0; i<setsize; i++) {
			result[idx] = arr[i];
			ncr(idx+1);
		}
	}
}

 

처음엔 이런식으로 N개의 숫자를 담을때 hashset으로 중복을 제거시키고 배열에 담았다. 

그리고 중복을 허용하는 순열을 출력하도록 했더니 시간 초과가 발생했다. 

반대로 순서를 바꿔서 일단 N개의 숫자를 N 크기의 배열에 담고, 

순열을 출력하는 과정에서 이미 출력된 적이 있는 형태의 배열이라면 출력하지 않도록, 중복을 허용하지 않도록 했더니 해결되었다. 

 

SOLVE

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

public class Main {
	static int[] arr;
	static int N, M;
	static int[] result;
	static Set<String> set;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		set = new HashSet<>();
		
		String[] input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		
		arr = new int[N];
		result = new int[M];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) arr[i] = Integer.parseInt(st.nextToken());
		
		Arrays.sort(arr);
		ncr(0);
		System.out.println(sb);
	}
	public static void ncr(int idx) {
		if(idx == M) {
			StringBuilder tmp = new StringBuilder();
			for(int a : result) tmp.append(a).append(" ");
			tmp.append('\n');
			String str = tmp.toString();
			
			if(!set.contains(str)) {
				set.add(str);
				sb.append(tmp);
			}
			return;
		}
		
		for(int i=0; i<N; i++) {
			result[idx] = arr[i];
			ncr(idx+1);
		}
	}
}