728x90
https://www.acmicpc.net/problem/10973
10973번: 이전 순열
첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
// 코드
|
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
|
import java.util.*;
import java.io.*;
public class Main{
static int n;
public static void main(String[] args) throws Exception {
// Please Enter Your Code Here
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
n = Integer.parseInt(br.readLine());
int[] num = new int[n];
st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) {
num[i] = Integer.parseInt(st.nextToken());
}
boolean resFlag = nextPermutation(num);
if(resFlag) {
for(int i=0; i<n; i++) {
bw.write(num[i] + " ");
}
} else {
bw.write(String.valueOf(-1));
}
br.close();
bw.flush();
bw.close();
}
public static boolean nextPermutation(int[] num) {
// 맨 오른쪽을 가르킨다.
int rightCursor = n-1;
// 오른쪽에서부터 탐색하면서 i보다 i-1가 더 큰경우를 찾는다.
while(rightCursor>0 && num[rightCursor-1]<=num[rightCursor]) rightCursor--;
if(rightCursor<=0) return false;
// 오른쪽에서부터 탐색하면서 rightCursor-1보다 newRightCursor가 더 작은 경우를 찾는다.
int newRightCursor = n-1;
while(num[rightCursor-1]<=num[newRightCursor]) newRightCursor--;
// 위치를 바꾸어준다.
int temp = num[rightCursor-1];
num[rightCursor-1] = num[newRightCursor];
num[newRightCursor] = temp;
// 정렬한다.
for(int i=rightCursor; i<n-1; i++) {
for(int j=i+1; j<n; j++) {
if(num[i] < num[j]) {
int temp2 = num[i];
num[i] = num[j];
num[j] = temp2;
}
}
}
return true;
}
}
|
cs |
반응형