공부 164일차: 백준 10972번 다음 순열 자바 java

10972 다음 순열

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

 

 

 

---

백준 10972번 문제 다음 순열

---

문제

---

 

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/290

공부 152일차: 백준 15649번 N과 M (1) 자바 java

이 DFS 문제를 활용하면 되겠다 싶었다

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, count;
    static int[] arr, nums;
    static boolean[] visited;
    static int[][] permutation;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        
        arr = new int[n];
        nums = new int[n];
        visited = new boolean[n];
        permutation = new int[getSize()][n];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        
        getPermutation(0);
        
        for(int i = 0; i < getSize(); i++) {            
            if(Arrays.equals(permutation[i], nums)) {    // 같으면
                if(i+1 >= getSize()) {
                    System.out.println(-1);
                }else {                    
                    for(int val : permutation[i+1]) {
                        System.out.print(val+" ");// 배열 모두 출력하고
                    }                    
                }
                return;    // 반복문 종료
            }
        }
        
    }
    
    // 배열 개수 구하기
    public static int getSize() {
        int[] dp = new int[10_001];
        dp[2] = 2;
        for(int i = 3; i < n+1; i++) {
            dp[i] = dp[i-1]*i;
        }
        return dp[n];
    }
    
    // DFS 활용하여 전체 순열 구하기
    public static void getPermutation(int depth) {
        // 입력된 숫자의 깊이까지의 배열 출력
        if(depth == n) {
            if(count < getSize()) {                
                for(int i = 0; i < n; i++) {
                    permutation[count][i] = arr[i];
                }
            }
            count++;
            return;        // 멈추기
        }
        
        for(int i = 0; i < n; i++) {
            // 방문하지 않은 노드라면
            if(!visited[i]) {
                visited[i] = true;    // 방문상태로 변경 후     
                arr[depth] = i+1;     // 그 깊이의 노드에 값 넣기
                getPermutation(depth+1);    // 다음 노드 : 깊이+1
                visited[i] = false;    // 다시 false로 돌려서 검사할 수 있도록
            }
        }
    }
 
}

 

그래서 점화식을 통해 총 몇 개의 순열이 나오는지 구하고,

전체 순열을 구하는 메서드를 구현하여 입력한 순열과 비교해보았는데, 시간 초과가 떴다

 

고민하다가 https://dding9code.tistory.com/8 이 블로그를 참고했다

 

---

정답 인정 코드

---

 

 

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int[] nums;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        nums = new int[n];
 
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        
        if(nextPermutation()) {    // 그 다음 순열이 존재한다면
            for(int val : nums) {
                bw.write(val+" ");
            }
        }else {
            bw.write("-1");
        }
        bw.flush();
        bw.close();
        
    }
    
    // 다음 순열 있는지 체크
    public static boolean nextPermutation() {
        
        int i = nums.length - 1;
        while(i > 0 && nums[i-1] >= nums[i]) {    // 내림차순이 되기 직전의 자리 찾기
            i--;
        }
        if(i < 1) {    // i == 0 --> 전체 내림차순(즉, 가장 마지막 순열)
            return false;
        }
        
        int j = nums.length - 1;
        while(nums[i-1] >= nums[j]) {    // 내림차순 되기 직전 수 +1 찾기
            j--;
        }
        
        swap(i-1, j);    // 자리 바꾸기
        
        j = nums.length-1;
        
        while(i < j) {
            swap(i, j);
            i++;
            j--;
        }
        return true;
    }
    
    
    // 자리 바꾸기
    public static void swap(int n, int m) {
        int temp = nums[n];
        nums[n] = nums[m];
        nums[m] = temp;
    }
 
}

 

내가 푼 코드는 시간 초과가 떠서 아쉽긴 하지만,

다음 순열을 어떻게 구하는지 원리를 알 수 있었다

 

 

 

---