BOJ#10972 다음 순열
* 문제
* 풀이
순열 설명
순열 설명(사전순)
쉬운 것 같으면서도 어려운 문제였습니다.
문제 해결 알고리즘은 다음과 같습니다.
위 순열 설명 링크와 순열 설명(사전순) 링크를 다 읽으셨다는 가정 하에 설명해보겠습니다.
,
A = [1, 3, 4, 2]
주어진 순열의 끝을 idx로 지정하고, A[idx-1] < A[idx] 일때까지 idx를 줄여나갑니다.
int idx = N - 1;
while (idx > 0 && A[idx - 1] > A[idx]) idx--;
idx는 2가 되고 아래와 같이 두 부분으로 나눌 수 있습니다.
[1, 3 , | 4, 2]
위 과정으로 알아낸 것은
빨간색 부분은 내림차순으로 정렬된 부분이고 더 이상 경우의 수를 만들어 낼 수 없다는 것입니다.
(사전순으로 순열을 뽑아내므로 내림차순으로 된 부분은 더 이상 경우의 수를 만들 수 없다)
DFS를 통해 사전식 순열을 만들고 있기 때문에
우리가 원하는 '다음 순열'을 찾기 위해서는
이전 depth로 돌아간 후 해당 depth에서 다음 iteration을 동작시키면 됩니다.
즉, 현재 depth가 2 이므로 이전 depth인 1로 돌아가서 다음 iteration을 돌면
이전 depth에서
이전 iteration : [1, | 2, 3, 4]
: depth에서 depth까지 right rotate
현재 iteration : [1, | 3, 2, 4]
: depth에서 depth+1 까지 right rotate
다음 iteration : [1, | 4, 2, 3]
: depth에서 depth+2 까지 right rotate
우리가 원하는 답인 [1, 4, 2, 3]을 얻을 수 있습니다.
,
그리고 이전 depth로 돌아가서 다음 iteration을 동작할 때
right rotate 범위를 지정해줘야 합니다.
아래 코드가 right rotate 범위를 구하고 rightRotate 함수를 실행시키는 코드입니다.
int endIdx = N - 1;
while (endIdx >= idx && A[idx - 1] > A[endIdx]) endIdx--;
int iteration = N - 1 - endIdx;
Arrays.sort(A, idx - 1, A.length);
rightRotate(A, idx - 1, idx + iteration);
[1, 3 , | 4, 2]
A[idx-1] (보라색 원소)와 오른쪽 부분 원소를
오른쪽에서 왼쪽으로 비교해가면서 right rotate 범위를 구합니다.
(A[idx-1]보다 작은 원소가 오른쪽부터 몇개 있는지 확인)
위 예제에서는
rightRotate (start: idx-1, end: idx + 1)
즉 idx 1부터 3까지의 범위로 rightRotate 합니다.
[1, 2, 3, 4] -> [1, 4, 2, 3]
* 나의 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* BOJ#10972 다음 순열
* https://www.acmicpc.net/problem/10972
*/
public class Main {
public static void main(String[] args) throws IOException {
// input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] A = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
// Solve
int idx = N - 1;
while (idx > 0 && A[idx - 1] > A[idx]) idx--;
if (idx == 0) {
System.out.println(-1);
} else {
int endIdx = N - 1;
while (endIdx >= idx && A[idx - 1] > A[endIdx]) endIdx--;
int iteration = N - 1 - endIdx;
Arrays.sort(A, idx - 1, A.length);
rightRotate(A, idx - 1, idx + iteration);
printArr(A, N);
}
}
static void printArr(int[] A, int N) {
for (int i = 0; i < N; i++) {
System.out.print(A[i] + " ");
}
}
static void rightRotate(int[] A, int start, int end) {
int last = A[end];
for (int i = end; i > start; i--) {
A[i] = A[i - 1];
}
A[start] = last;
}
}