-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTest2.java
More file actions
90 lines (70 loc) · 2.4 KB
/
Copy pathTest2.java
File metadata and controls
90 lines (70 loc) · 2.4 KB
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package org.line;
import java.util.*;
import java.util.stream.Collectors;
/*
* 순열 : n 개 중에서 r개 선택
* 시간복잡도는 O(n!)
* 연습 문제 : https://www.acmicpc.net/problem/10974
*/
import java.util.stream.Stream;
public class Test2 {
public static List<Integer> quickSort(List<Integer> list) {
if (list.size() <= 1) return list;
int pivot = list.get(list.size() / 2);
List<Integer> lesserArr = new LinkedList<>();
List<Integer> equalArr = new LinkedList<>();
List<Integer> greaterArr = new LinkedList<>();
for (int num : list) {
if (num < pivot) lesserArr.add(num);
else if (num > pivot) greaterArr.add(num);
else equalArr.add(num);
}
return Stream.of(quickSort(lesserArr), equalArr, quickSort(greaterArr))
.flatMap(Collection::stream)
.collect(Collectors.toList());
}
static int location;
static int now = 0;
public static void main(String[] args) {
List<Integer> insertArr = new LinkedList<Integer>();
Scanner sc = new Scanner(System.in);
String insertNum = sc.nextLine();
String[] insertNums = insertNum.split(" ");
for(int i=0; i< insertNums.length; i++)
insertArr.add(Integer.parseInt(insertNums[i]));
insertArr = quickSort(insertArr);
int[] arr = new int[insertArr.size()];
int[] output = new int[insertArr.size()];
boolean[] visited = new boolean[insertArr.size()];
for(int i=0; i<insertArr.size(); i++)
arr[i] = insertArr.get(i);
location = sc.nextInt();
perm(arr, output, visited, 0, arr.length, 3);
}
static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
//- 현재 깊이는 뽑은 개수이다
//- 즉, 뽑은 개수와 뽑을 개수가 같다면 종료.
if(depth == r) {
now++;
if (now == location)
print(output,r);
return;
}
// 1. 모든 원소를 순회한다.
for (int i=0; i<n; i++) {
// 2. 방문하지 않은 원소를 찾는다
if(visited[i] != true) {
visited[i] = true; // 방문표시를 한다
output[depth] = arr[i]; // 결과값 배열의 해당깊이 위치에 방문하지 않은 원소 값 대입
perm(arr, output, visited, depth+1, n, r);
visited[i] = false;
}
}
}
// 배열 출력
static void print(int[] arr, int r) {
for(int i=0; i<r; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}