백준 10972 - 다음 순열
Updated:
Java
10972 번 - 다음 순열
문제
1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.
사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.
N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.
- 1, 2, 3
- 1, 3, 2
- 2, 1, 3
- 2, 3, 1
- 3, 1, 2
- 3, 2, 1
접근 방법
처음에는 DFS로 해결하려 하였지만, n이 최대 10000이므로 최악의 경우 모든 순열을 계산하면 10000!까지 생각해야 하므로 시간 초과가 날 수 밖에 없는 문제였다.
따라서 문제의 규칙을 보고 해결하였다.
N = 3인 경우보다 N이 4인 경우가 더 규칙을 찾기 쉬우므로, 이를 기준으로 설명하면
N=4 인 모든 순열 :
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
- 오른쪽에서 왼쪽으로 이동하면서 n과 n-1을 비교한다.
- n-1 < n인 경우를 찾는다. 찾은 인덱스를 기준으로 왼쪽 영역과 오른쪽 영역을 나눌 수 있다.
- 해당 인덱스에 있는 숫자를 기준으로 삼는다.
- 오른쪽 영역에서 오른쪽부터 왼쪽영역으로 움직이면서 기준 값과 크기를 비교한다.
- 크다면 자리를 바꾼다.
- 오른쪽영역의 숫자를 오름차순으로 정렬해준다.
- 만약 4 3 2 1과 같이 마지막 순열이면 위 2~6번 과정을 거치지 않으므로, 이를 확인한다.
코드
/*
2504번 - 괄호의 값
https://www.acmicpc.net/problem/2504
*/
import java.util.*;
import java.io.*;
public class Main {
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 초기화
n = stoi(br.readLine());
int[] perm = new int[n];
StringTokenizer stk = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
perm[i] = stoi(stk.nextToken());
}
boolean isFinded = false;
// 1번 : 오른쪽 끝에서 부터 탐색
end: for(int i = n - 1; i >= 1; i--) {
// 2번 : i-1 < i인 경우
if(perm[i] > perm[i-1]) {
int strd = i - 1; // 3번 : 해당 값을 기준(standard)으로 정한다
for(int j = n - 1; j >= i; j--) {
// 4번 : 오른쪽부터 왼쪽영역으로 움직이면서 기준 값과 크기를 비교
if(perm[strd] < perm[j]) {
// 5번 : 크다면 자리를 바꾼다.
int temp = perm[strd];
perm[strd] = perm[j];
perm[j] = temp;
// 6번 : 오른쪽영역의 숫자를 오름차순으로 정렬해준다.
int[] forsort = new int[n-i];
for(int k = 0; k < n-i; k++)
forsort[k] = perm[i+k];
Arrays.sort(forsort);
for(int k = i; k < n; k++)
perm[k] = forsort[k - i];
// 7번 : 다음 순열을 찾았으므로, 알려준다.
isFinded = true;
break end;
}
}
}
}
// 순열의 마지막 끝인 경우
if(!isFinded) {
System.out.println(-1);
br.close();
return;
}
for(int v : perm)
System.out.print(v + " ");
br.close();
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
DFS로 실패한 코드
import java.util.*;
import java.io.*;
public class Main {
static int n;
static boolean[] vis;
static int[] sel;
static int[] comp;
static int cnt = 0;
static ArrayList<Integer> result = new ArrayList<Integer>();
static boolean isSame = true;
static boolean getResult = false;
public static void main(String[] args) throws IOException {
//System.setIn(new FileInputStream("res/mainInput.txt")); //제출 할 때 주석해야함
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 초기화
n = stoi(br.readLine());
vis = new boolean[n + 1];
sel = new int[n];
comp = new int[n];
StringTokenizer stk = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
comp[i] = stoi(stk.nextToken());
}
// 순열 만들기
DFS(0);
if(result.size() == 0) {
System.out.println(-1);
br.close();
return;
}
for(int i = 0; i < n; i++) {
System.out.print(result.get(i) + " ");
}
System.out.println(cnt);
br.close();
}
static boolean DFS(int lv) {
if(lv == n) {
cnt++;
if(getResult) { // 다음 순열을 저장한다.
for(int i = 0; i < n; i++) {
result.add(sel[i]);
}
return true; // 다음 순열을 찾았으므로 DFS 종료
}
isSame = true;
for(int j = n - 1; j >= 0; j--) {
if(sel[j] != comp[j]) { // 주어진 순열 값과 같은지 바교
isSame = false;
break;
}
}
if(isSame) { // N개의 값이 같으면 다음 순열을 출력하도록 변수 값을 준다.
getResult = true;
}
return false;
}
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
vis[i] = true;
sel[lv] = i;
if(DFS(lv + 1)) {
return true;
}
vis[i] = false;
}
}
return false;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
난이도
★★★★★
후기
dfs 문제 일거 같았지만 완전히 속은 문제.
스터디를 통해 혹시 DFS로 해결하신 분이 있으신지 여쭤봐야겠다.
개선할 점
스스로 해결하지 못 푼 문제, 수학 / DP는 창의력을 떠올리기 너무 힘들다.
