백준 15649 N과 M (Java)

1. 문제 링크

15649번: N과 M (1)

 

2. 문제 및 입출력예제

 

3. 문제 풀이

순열을 구하는 대표적인 문제이다.

input 배열은 1부터 N까지의 자연수가 들어간다.

isSelected는 선택된 수인지 아닌지 boolean값으로 판단한다.

선택되지 않은 숫자의 경우 numbers에 넣고 isSelected를 true로 바꿔 선택했음을 알린다.

permutation 재귀를 통해 종료되기 전까지 반복한 후에 isSelected를 false로 바꾸면 끝이다.

 

4. 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	private static StringBuilder sb = new StringBuilder();
	private static int N;
	private static int M;
	private static int[] input;
	private static int[] numbers;
	private static boolean[] isSelected;
	private static ArrayList<int[]> list = new ArrayList<>();
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();

		input = new int[N];
		numbers = new int[M];
		isSelected = new boolean[N+1];
		
		for(int i=0;i<N;i++) {
			input[i] = i+1;
		}
		
		permutation(0);

		for(int[] numbers : list) {
			for(int i=0;i<numbers.length;i++) {
				sb.append(numbers[i]+" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
		sc.close();
	}


	private static void permutation(int c) {
		if(c == M) {
			list.add(Arrays.copyOfRange(numbers, 0, numbers.length));
			return;
		}
		
		for(int i=0;i<N;i++) {
			if (isSelected[i]) {
				continue;
			}

			numbers[c] = input[i];
			isSelected[i] = true;;
			permutation(c+1);
			isSelected[i] = false;
		}	
	}
}