[백준] 15666번 : N과 M(12) - 자바(JAVA)

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

15666번: N과 M (12)

 

문제 해석

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구해야 합니다.

 

조건

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

2. 같은 수를 여러 번 골라도 된다. ( 중복 가능)

3. 고른 수열은 비 내림차순이어야 한다. ( 오름차순으로 정렬되어야 함)

ex) 1 1 2 2 3 3 4 4

 

문제 풀이 전 설계

항상 N개의 자연 수중에 1개씩 M번 뽑아서 수열을 생성합니다.

같은 수를 여러 번 골라도 되나 중복되는 수열은 출력하면 안 되기 때문에 중복 조합을 사용합니다.

이후에 오름차순으로 sort 해서 출력합니다.

N과 M의 범위가 작으며 시간제한이 2초이기 때문에 완전 탐색이 무리 없을 것으로 예상됩니다.

 

풀이하면서 고민한 점

Set <int []> 를 사용하려고 했으나 Set <T>의 T가 int형 배열이기 때문에 hashCode도 다르고 equals도 달라서 같은 값이 중복해서 Set에 들어가게 되었습니다.

Wrapper 클래스를 사용하여 equals 메서드를 재정의하거나 Arrays.eqauls 메서드를 사용해야 합니다.

 

combination에서 i=start로 시작해야 하는데 i=0부터 시작하게 해서 시간 초과 오류가 계속 발생했었음.

 

우선 numArray가 정렬되어있기 때문에 가능합니다.

numArray가 {1, 1, 7, 9}라고 가정해보겠습니다.

for문에서 i번째 선택된 값을 before에 저장한 후 다음 반복에서 접근하는 값 i+1과 비교합니다.

따라서 0번째 1이 선택되면 1번째 1은 continue 되어 넘어가게 됩니다.

만약 before가 없다면 (1,7) (1,9)가 2번씩 나오게 됩니다.

 

ArrayList <int []>를 사용한 코드 : 756ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main_15666_N과M12 {

	static int N, M;
	static int[] numArray;
	static Set<int[]> set = new LinkedHashSet<int[]>();
	static List<int[]> nonDuplicateList = new ArrayList<int[]>();
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		numArray = new int[N];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			numArray[i] = Integer.parseInt(st.nextToken());
		}

		int[] combinatedArray = new int[M];

		// 문제 풀기전에 정렬
		Arrays.sort(numArray);
		combination(0, 0, combinatedArray);
		System.out.println(sb);
		
	}

	private static void combination(int cnt, int start, int[] combinatedArray) {
		if (cnt == M) {
			// 깊은 복사
			int[] clone = combinatedArray.clone();

			for (int[] tempArray : nonDuplicateList) {
				if (Arrays.equals(tempArray, clone)) {
					return;
				}
			}

			nonDuplicateList.add(clone);
			for (int intElement : clone) {
				sb.append(intElement + " ");
			}			
			sb.append("\n");
			return;
		}
		//int before = Integer.MIN_VALUE;
		for (int i = start; i < N; i++) {
			combinatedArray[cnt] = numArray[i];
			combination(cnt + 1,i, combinatedArray);
		}
	}

}

 

 

LinkedHashSet <String>을 이용한 코드 : 176ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main_15666_N과M12 {

	static int N, M;
	static int[] numArray;
	static Set<String> set = new LinkedHashSet<String>();
	static List<int[]> nonDuplicateList = new ArrayList<int[]>();
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		numArray = new int[N];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			numArray[i] = Integer.parseInt(st.nextToken());
		}

		int[] combinatedArray = new int[M];

		// 문제 풀기전에 정렬
		Arrays.sort(numArray);
		combination(0, 0, combinatedArray);
						
		System.out.println(sb);
		
	}

	private static void combination(int cnt, int start, int[] combinatedArray) {
		if (cnt == M) {
			StringBuilder temp = new StringBuilder();
			for(int i=0; i<cnt; i++) {
				temp.append(combinatedArray[i]).append(' ');
			}
			temp.append("\n");
			String str = temp.toString();
			if(set.contains(str)) {
				return;
			}
			
			set.add(str);
			sb.append(str);			
			return;
		}
		for (int i = start; i < N; i++) {
			combinatedArray[cnt] = numArray[i];
			combination(cnt + 1,i, combinatedArray);
		}
	}

}

 

백 트레킹을 통한 구현 : 152ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main_15666_N과M12 {

	static int N, M;
	static int[] numArray;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		numArray = new int[N];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			numArray[i] = Integer.parseInt(st.nextToken());
		}

		int[] combinatedArray = new int[M];

		// 문제 풀기전에 정렬
		Arrays.sort(numArray);
		combination(0, 0, combinatedArray);						
		System.out.println(sb);
		
	}

	private static void combination(int cnt, int start, int[] combinatedArray) {
		if (cnt == M) {
			for(int i=0; i<cnt; i++) {
				sb.append(combinatedArray[i]).append(' ');
			}
			sb.append("\n");						
			return;
		}
		int before = Integer.MIN_VALUE;
		for (int i = start; i < N; i++) {
			if(before == numArray[i]) continue;
			combinatedArray[cnt] = numArray[i];
			combination(cnt + 1,i, combinatedArray);
			before = numArray[i];
		}
	}

}