풀이
아이디어
다음 순열을 주어진 수 보다 큰 수입니다.
규칙을 한 번 찾아 봅시다.
1, 2, 3은 1, 3, 2로 바뀝니다.
2와 3의 위치가 바뀌었네요
1, 3, 2는 2, 1, 3으로 바뀝니다.
2, 1, 3은 2, 3, 1로 바뀝니다.
규칙을 살펴봅시다. 다음 순열과의 차이가 작기 때문에 뒤에서부터 비교하여 혹시 뒤에 있는 수가 앞의 있는 수보다 작다면 둘의 위치를 바꿔주는 것이 보여집니다.
1, 2, 3에서 2는 3보다 작았기 때문에 두 수의 위치가 바뀌면 커지겠죠
규칙 1. 앞에 있는 작은 수와 뒤에 있는 큰 수를 바꾼다.
그렇다면 1, 3, 2를 보고 규칙 1을 대입해봅시다.
뒤에서 부터 규칙 1을 봅니다. 3은 2보다 크니 넘어갑니다. 1은 3보다 작으니 바뀌어야 할 숫자를 찾았습니다. 하지만 1은 3과 2 둘 과 비교하여 작은데 무엇이랑 바꿔줘야 할까요?
답은 2랑 바꿔줘야 겠죠
2, 3, 1이 되어습니다. 하지만 2, 3, 1보다 2, 1, 3이 더 작은 수입니다.
이를 찾는 방법은 가장 뒤에 있는 1보다 큰 수를 찾으면 됩니다.
그게 가장 작은 수이기 떄문에 적게 변하는 방법입니다.
규칙 2. 뒤에 있는 수 중 앞에 있는 작은 수 보다 큰 수 중 제일 뒤에 있는 수를 바꿔줍니다.
2를 제외한 3, 1을 정렬을 해줘야 하는데 방법은 간단합니다. 뒤집어 주면 됩니다.
?? 왜 뒤집으면 되나요??
1, 3, 2에서 1이 바뀌어야 되는 수가 되었다는 것은 1에 도달하기 전까지 숫자들이 감소하는 모습이었습니다.(내림차순)
이제 바뀌는 수가 바뀌었기 때문에 그 수 이후로는 가장 작은 수가 와야 합니다.
가장 작은 수는 결국 오름차순인데 그렇다면 내림차순을 반대로 뒤집으면 문제는 해결이 됩니다.
규칙 3. 바뀐 수 뒤로는 뒤집어서 내림 차순을 오름 차순으로 만들기
이 아이디어를 통해서 문제를 풀어보자!
실제 구현
규칙 1. 앞에 있는 작은 수와 뒤에 있는 큰 수를 바꾼다.
// 규칙 1. 앞에가 뒤에 보다 작은 수 찾기
int i = N-1;
while(i>0 && arr[i-1] > arr[i])
i--;
// i가 0이라면 모든 배열이 내림차순이다.
// 즉 배열 중에 가장 큰 수이다.
if(i==0)
return false;
규칙 2. 뒤에 있는 수 중 앞에 있는 작은 수 보다 큰 수 중 제일 뒤에 있는 수를 바꿔줍니다.
int j = N-1;
// 규칙 2 arr[i-1]보다 큰 수 중에 가장 뒤에 있는 수(가장 작은 수)를 찾기
while(arr[j] <= arr[i-1]) {
j--;
}
swap(i-1, j);
규칙 3. 바뀐 수 뒤로는 뒤집어서 내림 차순을 오름 차순으로 만들기
// 규칙 3. 내림차순으로 가장 큰 수이기 때문에 오른차순으로 가장 작은 수로 바꾸기
j = N-1;
while(i < j) {
swap(i, j);
i++;
j--;
}
return true;
코드
package ThisWeek38;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class No10972 {
static int N;
static int[] arr;
public static void main(String[] args) throws IOException {
input();
pro();
}
private static void pro() {
StringBuilder sb = new StringBuilder();
if(check()) {
for(int i : arr) {
sb.append(i + " ");
}
}
else
sb.append(-1);
System.out.println(sb);
}
private static boolean check() {
// 규칙 1. 앞에가 뒤에 보다 작은 수 찾기
int i = N-1;
while(i>0 && arr[i-1] > arr[i])
i--;
// i가 0이라면 모든 배열이 내림차순이다.
// 즉 배열 중에 가장 큰 수이다.
if(i==0)
return false;
int j = N-1;
// 규칙 2 arr[i-1]보다 큰 수 중에 가장 뒤에 있는 수(가장 작은 수)를 찾기
while(arr[j] <= arr[i-1]) {
j--;
}
swap(i-1, j);
// 규칙 3. 내림차순으로 가장 큰 수이기 때문에 오른차순으로 가장 작은 수로 바꾸기
j = N-1;
while(i < j) {
swap(i, j);
i++;
j--;
}
return true;
}
private static void swap(int j, int i) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
br.close();
}
}
