[Java] 순열

순열 : 서로다른 N개의 원소에서 R개를 중복없이 순서에 상관있게 선택하는 것

 

[입력] : 4개 원소(1,2,3,4)중에서 2개뽑기

4 2

1 2 3 4

 

[출력]

[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, R : 존재하는 원소의 수, 뽑을 원소의 갯수

- input : 존재하는 원소들을 담고있는 배열

- numbers : 뽑은 원소들을 담고있는 배열

- isSeletcted : 중복을 방지하기 위해 선택된 수의 정보를 표시하는 배열

- cnt : 뽑은갯수를 파악하기 위한 인자값

 

[풀이]

재귀를 이용해서 순열을 구현한다.

첫번째 원소부터 마지막원소까지 접근할 수 있어야 하므로, 반복문을 N번까지 돌린다. 

이 원소가 선택된 원소인지 체크하고, 아니라면 선택수 배열에 넣어준다. 그리고 뽑은갯수에 1더해주고 재귀를 탄다. 

이때 재귀에서 나오면 중복체크 한 원소는 다시 원래대로 복구해야함에 주의한다. 

ex) 1,2 -> 1,3 으로 갈 때, 2는 풀어줘야 한다 .

그리고 뽑은 개수가 R개가 되면 출력하고 return한다.

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

//nPr
//n개의 수 입력받아 처리
public class PermutationTest {
	static int N, R;
	static int[] input, numbers; // input : 입력수배열, numbers:선택수배열
	static boolean[] isSelected;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		R = sc.nextInt();

		input = new int[N];
		numbers = new int[R];
		isSelected = new boolean[N];

		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
		}

		permutation(0);
		
		
	}

	// 현재 자리에 수 뽑기
	public static void permutation(int cnt) { // cnt : 인덱스로 쓰지만 "직전까지 뽑은 수의 개수"라고 생각하면 좋음

		// 기본파트
		if (cnt == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		// 입력받은 모든 수를 현재 자리에 넣어보기
		for (int i = 0; i < N; i++) {
			// 기존 자리의 수들과 중복되는지 체크
			if (isSelected[i])
				continue;
			numbers[cnt] = input[i];
			isSelected[i] = true;
			// 다음 수 뽑으러 가기
			permutation(cnt + 1); // cnt++; 하는순간 cnt 값 바뀌기 때문에 안됨.
			isSelected[i] = false; // 세번째 숫자 리셋->두번째 리셋 -> 첫번째 리셋 (첫번째자리부터 다시뽑기)
		}
	}

}