https://www.acmicpc.net/problem/10972규칙
1. 오른쪽에서 왼쪽으로 이동하면서 n과 n-1을 비교한다.
2. n-1 < n인경우를 찾는다. 찾은 인덱스를 기준으로 왼쪽 영역과 오른쪽 영역을 나눌 수 있다.
ex) 12543 --> 12 543
123645987 --> 123645 987
3. 해당 인덱스에 있는 숫자를 가지고 오른쪽 영역에서 오른쪽부터 왼쪽영역으로 움직이면서 크기를 비교한다.
4. 크다면 자리를 바꾼다.
5. 오른쪽영역의 숫자를 오름차순으로 정렬해준다.
글보다 숫자로 표기하면 더 이해하기 쉽다.
입력 : 326154
--> 3261 54 (영역 나누기)
--> 3261 54 (크기 비교하기)
--> 3264 51 (자리 바꾸기)
--> 3264 15 (오름차순 정렬)
출력 : 326415
10972번: 다음 순열
첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//다음 순열
public class Baekjoon10972 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int arr[] = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
if (nextPermutation(arr)) {
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
} else {
System.out.println("-1");
}
}
public static boolean nextPermutation(int[] arr) {
//뒤에서부터 탐색하면서 a-1보다 a가 더 큰 경우 찾음
int a = arr.length - 1;
while(a > 0 && arr[a-1] >= arr[a]) a--;
if (a <= 0 ) return false;
//다시 뒤에서부터 탐색하며 a-1보다 b가 더 큰 경우 찾음
int b = arr.length - 1;
while(arr[a-1] >= arr[b]) b--;
//a랑 b를 swap
int tmp = arr[a-1];
arr[a-1] = arr[b];
arr[b] = tmp;
//a에서부터 끝까지를 오름차순 정렬
int start = a;
int end = arr.length - 1;
while(start < end) {
tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
start++;
end--;
}
return true;
}
}
|
|
'알고리즘' 카테고리의 다른 글
| [Java]백준 1120 문자열 (그리디문제) (0) | 2020.02.02 |
|---|---|
| [프로그래머스] 완주하지 못한 선수 (자바_Java) (0) | 2019.10.04 |
| [Java]백준 10973 이전순열 (0) | 2019.07.07 |
