[백준] 10974번 - 이전 순열 (JAVA)
[접근 방법]
바로 이전 문제인 <다음 순열> 문제를 정확히 반대되는 문제이다.
<입력값>
7
3 2 7 1 4 5 6
주어진 순열 : [ 3 , 2 , 7 , 1 , 4 , 5 , 6 ]
1. 주어진 순열에 마지막 원소를 포함하는 <가장 긴 증가 수열> 을 찾는다.
(A[i] < A[i-1] 인 가장 큰 i 를 찾는다.)
[ 3 , 2 , 7 , 1 , 4 , 5 , 6 ]
i = 3 (A[i] = 1 < A[i-1] = 7)
2. j >= i 이고, A[j] < A[i-1] 인 가장 큰 j 를 찾는다.
[ 3 , 2 , 7 , 1 , 4 , 5 , 6 ]
j = 6 (A[j] = 6 < A[i-1] = 7)
3. SWAP (A[i-1] , A[j])
[ 3 , 2 , 6 , 1 , 4 , 5 , 7 ]
4. A[i] ~ A[N-1] reverse
[ 3 , 2 , 6 , 7 , 5 , 4 , 1 ]
주어진 수열 : [ 3 , 2 , 7 , 1 , 4 , 5 , 6 ] 의
이전 수열 : [3 , 2 , 6 , 7 , 5 , 4 , 1]
[JAVA 코드]
// 10973번 - 이전 순열
import java.util.*;
import java.io.*;
public class Main {
static int[] arr;
static int N;
static boolean flag;
public static void PrePermutation(int[] Array){
int idx = Array.length - 1;
// 1. Array[idx] < Array[idx - 1] 인 가장 큰 idx 구하기
while(idx > 0 && Array[idx] >= Array[idx - 1]){
idx = idx - 1;
}
// 주어진 순열이 내림차순인 경우
if (idx == 0){
flag = false;
return;
}
// 2. j >= idx 이고, Array[j] < Array[idx-1] 인 가장 큰 j 구하기
int j = Array.length - 1;
while(Array[idx - 1] <= Array[j]){
j = j - 1;
}
// 3. SWAP (Array[idx - 1], Array[j])
int temp = Array[idx - 1];
Array[idx - 1] = Array[j];
Array[j] = temp;
// 4. Array[idx] ~ Array[N-1] reverse
j = Array.length - 1;
while(idx < j){
temp = Array[idx];
Array[idx] = Array[j];
Array[j] = temp;
idx = idx + 1;
j = j - 1;
}
flag = true;
return;
}
public static void main(String[] args) throws IOException {
// 0. 입출력 선언 / 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
arr = new int[N];
for(int k=0; k<N; k++){
arr[k] = Integer.parseInt(st.nextToken());
}
PrePermutation(arr);
if (!flag){
bw.write("-1" + "\n");
}else {
for(int val : arr){
bw.write(val + " ");
}bw.write("\n");
}
bw.flush();
br.close();
bw.close();
}
}[Rewind]
1. 어려웠던 점
- 1 ~ 4의 방법을 즉각적으로 떠올리는 것이 어려웠음.
2. 알게된 점
- 이전 수열, 다음 수열을 구하는 방법을 이해하였음.
3. 개선 방향
- 같은 문제를 반복하여 풀어서 숙달해야 함.
