15663~15666_ N과 M (9)~(12) (JAVA)

1d-1c/BOJ

15663~15666_ N과 M (9)~(12) (JAVA)

yeon_11 2020. 11. 13. 00:12

15663_N과 M (9) : 순열

15663번: N과 M (9)

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

www.acmicpc.net

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static int N;
	static int M;
	static StringBuilder sb = new StringBuilder();
    static LinkedHashSet<String> result = new LinkedHashSet<>();
    
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());

		StringTokenizer st2 = new StringTokenizer(br.readLine());
		int[] num = new int[N];
		boolean[] checked = new boolean[N];

		List<Integer> temp = new ArrayList<>();

		for(int i=0; i<N; i++){
			num[i] = Integer.parseInt(st2.nextToken());
		}
		Arrays.sort(num);

		permutation(num, temp, checked);

		Iterator<String> it = result.iterator();
		while(it.hasNext()){
			sb.append(it.next()).append('\n');
		}
		System.out.print(sb);
	}

	private static void permutation(int[] num, List<Integer> temp, boolean[] checked){
		if(temp.size() == M){
			String str = "";
			for(int i=0; i<temp.size(); i++){
				str += temp.get(i)+" ";
			}
			result.add(str);
			return;
		}

		for(int i=0; i<num.length; i++){
			if(!checked[i]){
				checked[i] = true;
				temp.add(num[i]);
				permutation(num, temp, checked, result);

				checked[i] = false;
				temp.remove(temp.size()-1);
			}
		}
	}
}

15664_N과 M (10) : 조합

15664번: N과 M (10)

www.acmicpc.net

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static int N;
	static int M;
	static StringBuilder sb = new StringBuilder();
	static LinkedHashSet<String> result = new LinkedHashSet<>();
    
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());

		StringTokenizer st2 = new StringTokenizer(br.readLine());
		int[] num = new int[N];
		int[] temp = new int[M];

		for(int i=0; i<N; i++){
			num[i] = Integer.parseInt(st2.nextToken());
		}
		Arrays.sort(num);

		combination(num, temp, 0, 0, 0);

		Iterator<String> it = result.iterator();
		while(it.hasNext()){
			sb.append(it.next()).append('\n');
		}
		System.out.print(sb);
	}

	private static void combination(int[] num, int[] temp, int num_index, int temp_index, int cnt){
		if(cnt == M){
			String str = "";
			for(int i=0; i<temp.length; i++){
				str += temp[i]+" ";
			}
			result.add(str);
			return;
		}

		if(num_index >= N)
			return;

		temp[temp_index] = num[num_index];
		combination(num, temp, num_index+1, temp_index+1, cnt+1);
		combination(num, temp, num_index+1, temp_index, cnt);
	}
}

15665_N과 M (11) : 중복 순열

15665번: N과 M (11)

www.acmicpc.net

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static int N;
	static int M;
	static StringBuilder sb = new StringBuilder();
	static LinkedHashSet<String> result = new LinkedHashSet<>();

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());

		StringTokenizer st2 = new StringTokenizer(br.readLine());
		int[] num = new int[N];
		List<Integer> temp = new ArrayList<>();

		for(int i=0; i<N; i++){
			num[i] = Integer.parseInt(st2.nextToken());
		}
		Arrays.sort(num);

		permutation(num, temp);

		Iterator<String> it = result.iterator();
		while(it.hasNext()){
			sb.append(it.next()).append('\n');
		}
		System.out.print(sb);
	}

	private static void permutation(int[] num, List<Integer> temp){
		if(temp.size() == M){
			String str = "";
			for(int i=0; i<temp.size(); i++){
				str += temp.get(i)+" ";
			}
			result.add(str);
			return;
		}

		for(int i=0; i<num.length; i++){
			temp.add(num[i]);
			permutation(num, temp);
			temp.remove(temp.size()-1);
		}
	}
}

15666_N과 M (12) : 중복 조합

15666번: N과 M (12)

www.acmicpc.net

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static int N;
	static int M;
	static StringBuilder sb = new StringBuilder();
	static LinkedHashSet<String> result = new LinkedHashSet<>();

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());

		StringTokenizer st2 = new StringTokenizer(br.readLine());
		int[] num = new int[N];
		int[] temp = new int[M];

		for(int i=0; i<N; i++){
			num[i] = Integer.parseInt(st2.nextToken());
		}
		Arrays.sort(num);

		combination(num, temp, 0, 0, 0);

		Iterator<String> it = result.iterator();
		while(it.hasNext()){
			sb.append(it.next()).append('\n');
		}
		System.out.print(sb);
	}

	private static void combination(int[] num, int[] temp, int num_index, int temp_index, int cnt){
		if(cnt == M){
			String str = "";
			for(int i=0; i<temp.length; i++){
				str += temp[i]+" ";
			}
			result.add(str);
			return;
		}
		if(num_index >= N)
			return;

		temp[temp_index] = num[num_index];
		combination(num, temp, num_index, temp_index+1, cnt+1);
		combination(num, temp, num_index+1, temp_index, cnt);
	}
}

Set

- Set 컬렉션 클래스 : HashSet, TreeSet, LinkedHashSet

순열 nPr

① 순열 : 순서O, 중복X ('중복'은 자기자신 포함 여부를 의미) 예) 1,2,3,4 중 2개 뽑는 경우 (1,2) (1,3) (1,4) (2,1) (2,3) (2,4) (3,1) (3,2) (3,4) (4,1) (4,2) (4,3) /* N : 총 숫자 개수(num.length)..

yeone2ee.tistory.com

조합 nCr

조합 : 순서X, 중복X ('중복'은 자기자신 포함 여부를 의미) 예) 1,2,3,4 중 2개 뽑는 경우 (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) /* N : 총 숫자 개수(num.length) R : 숫자 중에서 뽑는 개수 (nCr에서 r을..

yeone2ee.tistory.com

저작자표시 비영리 변경금지

'1d-1c > BOJ' 카테고리의 다른 글

10026_적록색약 (JAVA) (0)	2020.11.16
10819_차이를 최대로 (JAVA) (0)	2020.11.15
15654~15657_N과 M (5)~(8) (JAVA) (0)	2020.11.11
15649~15652_N과 M (1)~(4) (JAVA) (0)	2020.11.11
4963_섬의 개수 (JAVA) (C++) (0)	2020.11.09

현재글15663~15666_ N과 M (9)~(12) (JAVA)

백수연