[백준BOJ] 15654번 N과 M(5).java

 

백준 저지에서 N과 M(5)을 자바를 통해 풀어 보았다. 

 

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

15654번: N과 M (5)

 

15654번 N과 M(5).java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

15654번 N과 M(5)

문제

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

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

설명

백트래킹을 사용하여 순열로 풀 수 있다.

 

추가로 StringBuilder를 사용하면 훨씬 더 빠르게 풀 수 있다.

코드

//15654번 N과 M(5).java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class N과_M5_15654 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[] num = new int[N];
		st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<N;i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(num);
		backtracking(num, N, M, 0, new int[N], new boolean[N]);
		System.out.println(sb.toString());
	}
    static void backtracking(int[] num, int N, int M,int count, int[] arr, boolean[] visit) {
    	if(count==M) {
    		for(int i=0;i<M;i++)sb.append(arr[i]+" ");
    		sb.append("\n");
    		return;
    	}
    	for(int i=0;i<N;i++) {
    		if(!visit[i]) {
    			visit[i]=true;
    			arr[count] = num[i];
    			backtracking(num, N, M, count+1, arr, visit);
    			visit[i]=false;
    		}
    	}
    }
}