순열, 조합 자바로 코딩(JAVA)

 

엊그제 풀던 프로그래머스 레벨2 양궁문제에서 많이 막혀서 순열, 조합 개념을 다시 잡고가야할 필요성을 느꼈다.

 

따라서 하나하나 다시 코딩을 해보면서 이해하는 시간을 가져야 되겠다.

 

하나하나 순서대로 코딩을 하는 모습을 캡처해서 코드를 완성해나가겠다.

 

순열

서로다른 N개 중에 R 개를 뽑는다. 순서는 {1,2} {2,1} 두개의 경우는 다른 경우로 친다.

 

일단 메인 실행문이다. 이제 여기에 permutation 이라는 재귀함수를 만들어 이를 통해 순열을 완성할 것이다.

 

15 번째 줄을 보면 재귀를 계속 돌릴 때 저러한 알고리즘으로 돌려야한다. 저 부분을 약간 수정을 해주어야 하는데 그부분은 visited 와 answer 이다.

 

visited 는 반복을 돌리면서 하나하나 방문을 해야한다. 예를 들어 {1, 2 ...} {1, 3} {1, 4} {1, 5} 이렇게 2 3 4 5 이렇게 높아지니 반복으로 이렇게 올려주는 작업을 해야한다는 뜻이다. 또한 {1, 2, 1} 이나 {1, 2, 2} 이렇게 중복인 숫자가 들어가면 안됨으로 visited 배열을 통해 방문 체크를 해주고 중복이 아닐 경우에만 넣어준다.

 

이부분을 추가한 코드는 이와 같다.

 

19번째 줄부터 반복문을 추가하고 이후 20번째 줄에서 if 조건을 통해 사용하지 않은 경우에만 사용한다는 조건을 걸어준다.

그 뒤 21 번째 줄에서 방문했다는 흔적? 을 남기고

22번째줄 ----이게 핵심코드중에 하나다. answer 배열에 arr[i]에 있는 원소를 넣어준다.

그 뒤 재귀를 돌려주고

24번째줄에서 재귀 전체를 빠져나올때 모든 visited 배열을 초기화 해준다. 그래야 다른 재귀에서 다시 방문해서 찾을 수 있다.

24번째 줄이 헷갈릴 수 있는데 예를들어 설명하자면 저코드를 수행했을 때 콘솔창에 표시되는 것은 이와같다.

1 2 로 하나의 묶음을 완성시키고 다음 반복에서 1 3 이 나와야하는데 만약 24번째 줄처럼 초기화 해주지 않는다면 1 3 중에 1은 다시는 나올 수가 없어진다. 

 

코드

package pro;

public class test16 {

	public static void main(String[] args) {
		int[] arr = {1,2,3}; // 처음 주어지는 배열 이 N 개의 정보가 들어간다.
		int r = 2; // 3개중에 몇개를 뽑을지 정해주는 변수 3개중에 3개를 뽑고싶으면 r = 3 으로 바꿔주면 된다.
		permu(arr, r, new boolean[arr.length], 0, new int[r]);
	}
	public static void permu(int []arr , int r, boolean[]visited, int depth, int []answer) {
		if(r == depth) { // 재귀의 종료조건 : 2개를 뽑았을때는 종료
			for(int a: answer) {
				System.out.print(a+" ");
			}
			System.out.println();
			return;
		}
		//재귀를 계속 돌릴때
		for(int i = 0; i< arr.length; i++) {
			if(!visited[i]) {
				visited[i] = true;
				answer[depth] = arr[i];
				permu(arr, r, visited, depth+1, answer);
				visited[i] = false;
			}
		}
	}

}

 

 

조합

조합은 N개중에 중에 R개를 중복허용하지 않고 뽑는것이다.
즉 1 2 는 2 1 과 같다고 본다.

 

9번째 줄을 보면 아까 8번째줄의 permu를 사용할 때보다 무언가 하나 더 추가된 모습을 볼 수 있다.

start 라는 변수인데

조합은 1 2 3 과 3 2 1 이 같다고 보기 때문에 1 2 3 하나만 존재하면 된다. 이것은 처음으로 오름차순으로 정렬이 되는 수를 뽑은 것으로 3이 가장 처음에 나온다면 3 4 5 이렇게 더 높은 숫자가 뒤에 올라와야 하는 현상을 이용한 것이다.

따라서 start를 각 재귀마다 1개씩 늘려 다음 재귀를 수행한다.

 

코드는 다음과 같다.

package pro;

public class test16 {

	public static void main(String[] args) {
		int[] arr = {1,2,3}; // 처음 주어지는 배열 이 N 개의 정보가 들어간다.
		int r = 2; // 3개중에 몇개를 뽑을지 정해주는 변수 3개중에 3개를 뽑고싶으면 r = 3 으로 바꿔주면 된다.
		combi(arr, r, new boolean[arr.length], 0, new int[r] , 0);
	}
	public static void combi(int[]arr, int r, boolean[]visited, int depth, int[]answer , int start) { // permu에서 start 라는게 추가되었다.
		//start의 역할은 조합에서 1 2 3 이나 3 2 1 은 같은것이다. 그러면 3 2 1 에서 3보다 낮은거는 아에 못나오게 하면 겹치는게 나오지않는다.
		// 즉 오름차순으로만 나오게 코드를 짜면 조합이 완성된다.
		// 오름차순으로만 나오게 코드를 짜기 위해 필요한 변수 start를 사용.
		if(r == depth) {
			for(int a : answer) {
				System.out.print(a + " ");
			}
			System.out.println();
			return;
		}
		for(int i = start ;i < arr.length; i++) {
			if(!visited[i]) {
				visited[i] = true;
				answer[depth] = arr[i];
				combi(arr, r, visited, depth+1, answer, start+1);
				visited[i] = false;
				
			}
		}
	}

}

 

해당 코드의 수행결과는 다음과 같다.

다음 시간에는 부분집합 구하는것과 중복순열, 중복 조합에 대해 포스팅 할 예정이다.