FilesExpand file tree

 master

/

Permutation2.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

68 lines (58 loc) · 1.86 KB

 master

/

Permutation2.java

Copy path

Top

File metadata and controls

• Code
• Blame

68 lines (58 loc) · 1.86 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

62

63

64

65

66

67

68

package org.study;

import java.util.*;

/**

* 순열 : n 개 중에서 r 개 선택

* 시간복잡도는 O(n!)

* 연습문제 : https://www.acmicpc.net/problem/10974

*/

public class Permutation2 {

public static void main(String[] args) {

int n = 3;

int[] arr = {1, 2, 3};

int[] output = new int[n];

boolean[] visited = new boolean[n];

perm(arr, output, visited, 0, n, 3);

System.out.println();

permutation(arr, 0, n, 3);

}

// 순서를 지키면서 n 개중에서 r 개를 뽑는 경우

// 사용 예시: perm(arr, output, visited, 0, n, 3);

static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {

if(depth == r) {

print(output, r);

return;

}

for(int i=0; i<n; i++) {

if(visited[i] != true) {

visited[i] = true;

output[depth] = arr[i];

perm(arr, output, visited, depth + 1, n, r);

visited[i] = false;

}

}

}

// 순서 없이 n 개중에서 r 개를 뽑는 경우

// 사용 예시: permutation(arr, 0, n, 4);

static void permutation(int[] arr, int depth, int n, int r) {

if(depth == r) {

print(arr, r);

return;

}

for(int i=depth; i<n; i++) {

swap(arr, depth, i);

permutation(arr, depth + 1, n, r);

swap(arr, depth, i);

}

}

static void swap(int[] arr, int depth, int i) {

int temp = arr[depth];

arr[depth] = arr[i];

arr[i] = temp;

}

// 배열 출력

static void print(int[] arr, int r) {

for(int i=0; i<r; i++)

System.out.print(arr[i] + " ");

System.out.println();

}

}