Algorithm 9일차

알고리즘에서 순열을 구현할 때 비트연산자를 활용할 수 있다.

대부분의 순열 문제 풀이는 10!까지 안전하다.
따라서 32bit인 int의 비트 연산으로 순열 조건 체크가 가능하다.

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

public class BitPermutation {
	static int N, R;
	static int[] numberArr, chaseArr;
	
	static void permutation(int cnt, int flag) { 
		if (cnt == R) {
			System.out.println(Arrays.toString(chaseArr));
			
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if ((flag & (1 << i)) != 0) {
				continue;
			}
			
			chaseArr[cnt] = numberArr[i];
			permutation(cnt + 1, flag | 1 << i);
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		R = sc.nextInt();
		
		numberArr = new int[N];
		chaseArr = new int[R];
		
		for (int i = 0; i < N; i++) {
			numberArr[i] = sc.nextInt();
		}
		
		permutation(0, 0);
		
		sc.close();
	}
}

해당 방법이 시간 복잡도에서 이점을 가지진 않지만, 공간 복잡도에서 이점을 가질 수 있다.

알고리즘에서 다음 순열을 효율적으로 구할 수 있다.

다음 순열의 예시는 아래와 같다.

1, 2, 3 의 다음 순열은 아래와 같다.
1, 2, 3 -> 1, 3, 2 -> 2, 1, 3 -> 2, 3, 1 -> 3, 1, 2 -> 3, 2, 1

다음 순열은 아래와 같이 구할 수 있다.

1. 뒤에서부터 해당 인덱스(i)와 해당 인덱스 - 1(i - 1)을 비교할 때
   해당 인덱스 값이 더 큰 인덱스(i)를 찾는다.
2. i - 1의 값보다 값이 큰 첫번째 인덱스(j)를 뒤에서부터 i 사이에서 찾는다.
3. i - 1과 j 간 값을 바꾼다.
4. i부터 배열 끝까지 오름차순 정렬한다.

이를 구현하면 아래와 같다.

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

public class NP {

	static void nextPer(int[] arr) {
		// 1. mount 잡기
		int mount = -1;
		
		for (int i = arr.length - 1; i > 0; i--) { 
			if (arr[i] >= arr[i - 1]) {
				mount = i;
				break;
			}
		}
		
		if (mount == -1) {
			return;
		}
		
		// 2. mount - 1을 잡고 첫번째 큰 값 위치를 잡는다.
		int oneChange = mount - 1;
		int twoChange = -1;
		
		for (int i = arr.length - 1; i > oneChange; i--) {
			if (arr[oneChange] <= arr[i]) {
				twoChange = i;
				break;
			}
		}
		
		// 3. oneChange랑 twoChange를 바꾼다.
		int temp = arr[oneChange];
		arr[oneChange] = arr[twoChange];
		arr[twoChange] = temp;
		
		// 4. mount부터 배열 끝까지 정렬한다.
		for (int i = mount; i < arr.length - 1; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[i] > arr[j]) {
					int t = arr[j];
					arr[j] = arr[i];
					arr[i] = t;
				}	
			}
		}
		
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		int[] arr = new int[N];
		
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		
		Arrays.sort(arr);
		
		int whole = 1;
		
		for (int i = 2; i <= arr.length; i++) {
			whole *= i;
		}
		
		for (int i = 0; i < whole; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(arr[j] + " ");
			}
			System.out.println();
			
			nextPer(arr);
		}
		
		sc.close();
	}
}

출력 결과는 아래와 같다.

4
1 2 3 4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1