반응형
nextPermutation 구현의 아이디어
nextPermuation이란 [1,2,3,4,5] ->[1,2,3,5,4] ->[1,2,4,3,5] 처럼 현재의 상태에서 다음 순열을 찾는 알고리즘이다.
물론 조합 알고리즘을 이용해서 각각의 인덱스의 조합을 이용해서 찾아도 되지만 더빠른 넥스트 퍼뮤테이션을 사용해야 할때가 있다.
기본 순열 1 3 5 4 2 에 대해서 예를 들어보자!
아래와 같은 순열이 이어저있을 때 nextPermutation은 다음과 같은 4가지 조건을 확인 하면된다.
모든 탐색은 오른쪽에서 왼쪽으로 시작한다.
1. arr[i-1] < arr[i] 이 오른쪽에서 왼쪽으로 탐색하면서 제일처음 나오는 값을 찾는다.
2. 이제 i-1를 비교하면서 arr[i-1] < arr[j] 를 만족하는 값을 찾는다. (오른쪽에서 왼쪽탐색시 처음나오는 값)
3. arr[i-1] 와 arr[j] 를 스왑한다.
4. i~N-1 까지의 순서를 reverse 해줍니다. (sort를 사용할 필요는 없고 양끝값을 swap해가면서 한칸식 줄여나갑니다)
아래와 같은 순열 있다고 생각하겠습니다.
arr[i-1] < arr[i] 를 만족하는 i-1를 찾는다.
arr[i-1] 기준으로 arr[j]를 만족하는 j값을 오른쪽부터 왼쪽으로 찾는다.
3. arr[i-1] 과 arr[j]를 swap
4. i~ j 까지의 순서를 reverse 해줍니다!
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
import java.util.Arrays;
public class PeumuTest {
static int N;
static int[] input;
static int totalCnt=0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
input = new int[N];
for (int i = 0; i < N; i++) {
input[i] = sc.nextInt();
}
// 시작 : 가장 작은 순열
do {
System.out.println(Arrays.toString(input));
}while(nextPemutation());
System.out.println("총 경우의 수 : "+totalCnt);
}
static boolean nextPemutation() {
totalCnt++;
// 맨 뒤부터 올라가면서 i-1<i 만족하는 것을 찾는다.
int i = N - 1;
// 현재의 내값보다 i-1이 커서 올라갈수 잇을때 까지 올라간다.
while (i > 0 && input[i - 1] >= input[i])
--i;
if (i == 0)
return false;
int j = N - 1;
// i 까지온다 왜냐 input[i-1] < input[i] 이기대문에 j는 최악의경우 i 까지온다.
while (input[i - 1] >= input[j])
--j;
//i-1 과 j 스왑한다.
int temp = input[i - 1];
input[i - 1] = input[j];
input[j] = temp;
int k = N-1;
while(i<k) {
temp = input[i];
input[i] = input[k];
input[k] = temp;
++i;
--k;
}
return true;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
출력은 do while 를 사용합니다. 이유는 nextPermutation은 다음 순열을 출력하기때문에 현재값을 출력을 하고 함수를 이용해서 다음 순열을 만듭니다.
while (input[i - 1] >= input[j]) 는 오른쪽 부터 탐색하면서 현재 i 가 i - 1 보다 더크다면 내려가는 구간 이기 때문에 i-- 하여서 다음 인덱스를 참고한다. while 문이 끝나면 arr[i-1] < arr[i]가 처음만족하는 배열이다.
만약 i = 0 이라면 현재 순열조합에서는 다음 순열을 찾을 수 없다. 따라서 false를 반환한다.
j값을 찾는것도 마찬가지다. j는 최악의 경우 i에서 멈춘다. 이유는 arr[i-1] < arr[i] 를 만족하는 값의 조건에서 찾는 것이기 때문이다.
그리고 arr[i-1] 과 arr[j]를 스왑한다.
이제 arr[i]~ arr[n-1] 를 역순으로 정렬한다.
k = n-1 이라고 할때
역순의 시작이 i 와 k 라고 한다면 두수를 스왑하고
i++; k--; 를 해주고 다시 스왑해서 i==k가 만날때 까지 해주면 그수는 reverese 형태를 띄게된다.
백준 문제로는 다음문제가 있다.
https://www.acmicpc.net/problem/10974
반응형
'Algorithm' 카테고리의 다른 글
LinkedList : java (0) | 2020.03.18 |
---|---|
파라메트릭 (0) | 2020.03.13 |
TreeSet : 트리에서 인덱스 번호 반환, 범위 값출력 (0) | 2020.03.06 |
Line Sweep 알고리즘 (백준 : 2261) JAVA (0) | 2020.03.06 |
Upper Bound, Lower Bound (0) | 2020.03.06 |