[JAVA][BOJ][S3] 15654. N과 M (5)

15654번: N과 M (5)

문제

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

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

입력

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

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

출력

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

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

풀이

순열을 이용해 풀면 되는 문제다

https://read-me.tistory.com/entry/%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9?category=1090596 

순열, 조합, 부분집합

윗 링크에서 순열, 조합, 부분집합 알고리즘에 대해 정리해 두었다

코드

package 문제풀이;

import java.io.*;
import java.util.*;

public class S3_15654_N과M5 {
	static int N, M;
	static int[] input, numbers;
	static boolean[] isSelected;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		input = new int[N];
		numbers = new int[M];
		isSelected = new boolean[N];
		
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(input);
		
		P(0);
		
		System.out.println(sb);
		
	}

	private static void P(int cnt) {
		if(cnt == M) {
			for (int i = 0; i < M; i++) {
				sb.append(numbers[i] + " ");
			}
			sb.append("\n");
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if(isSelected[i]) continue;
			numbers[cnt] = input[i];
			isSelected[i] = true;
			P(cnt+1);
			isSelected[i] = false;
		}
		
	}

}

결과

 

#자바 #java #boj #백준 #알고리즘