[백준BOJ] 15663번N과 M(9).java

 

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

 

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

15663번: N과 M (9)

15663번N과 M(9).java

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

 

15663번 N과 M(9)

문제

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

설명

N개의 자연수 중 M개를 고른 수열들을 순서대로 출력하는 문제이다. 백트래킹을 통해 풀 수 있다.

 

수열의 중복은 허용되지 않는다. 따라서 SET을 활용하여 중복이 발생하면 출력하지 않도록 했다.

코드

//15663번N과 M(9).java
package boj20211223;

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

public class N과M9_15663 {
	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);
		
		boolean[] visit = new boolean[N];
		HashSet<String> set = new HashSet<>();
		bt(0, N, M, visit, num, set, "");
		System.out.println(sb.toString());
	}
    
    static void bt(int count, int N, int M, boolean[] visit, int[] num, HashSet<String> set, String now) {
    	if(count==M) {
    		now = now.substring(1);
    		if(!set.contains(now)) {
    			sb.append(now+"\n");
    			set.add(now);
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		if(!visit[i]) {
    			visit[i]=true;
    			bt(count+1, N, M, visit, num, set, now+" "+num[i]);
    			visit[i]=false;
    		}
    	}
    }
}