[BOJ] 10974. 모든 순열

nextPermutation()을 구현하는 문제이다.

순열문제이다. 재귀적으로도 순열을 구현할 수 있으나, N의 범위를 고려하였을 때, 좋지 않은 방법이다. 이 문제는 c++에 존재하는 nextPermutation()을 구현하는 문제이다. c++은 구현되어 있기에 그냥 사용하면 몇줄로 끝나는 문제지만 java는 직접 구현해야 하기에 개념을 모른다면 까다로운 문제이다.

nextPermutation()은 다음과 같은 로직을 따른다.
1. 배열의 뒤쪽부터 탐색하며 꼭대기(i)를 찾는다. 즉, 뒤에서 부터 탐색하며 부등호가 > 에서 < 되는 지점을 찾는다.
2. 꼭대기(i)기준으로 교환인덱스를 i-1로 잡고, 뒤에서부터 탐색하며 arr[i-1]<arr[j] 를 만족하는 j를 찾는다.
3. arr[i-1]과 arr[j]를 교환한다.
4. i 부터 맨뒤 N-1까지 서로 교환해준다.

또한 배열에 중복되는 숫자가 있는 경우 무조건 nextPermutation()을 이용하여 구현해야한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

package online.base;   import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Main_bj_10974_모든순열 {     static int[] arr;     static int N;          public static void main(String[] args) throws Exception {         BufferedReader br =new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = null;                  N=Integer.parseInt(br.readLine());         arr=new int[N]; //        st=new StringTokenizer(br.readLine());         for(int i=0;i<N;i++) {             arr[i]=i+1;         }                    do {             for(int i=0;i<N;i++) {                 System.out.print(arr[i]+" ");             }             System.out.println();                      }while(nextPermutation());                  }          static boolean nextPermutation() {                  int i=N-1;             //1.등호가 < 되는 곳 찾기         while(i>0 && arr[i-1] >= arr[i])             i--;                  //i==0인경우 끝순열         if(i==0)             return false;                  //2.arr[i-1]보다큰 arr[j]찾기          int j= N-1;         while(arr[i-1]>=arr[j])             j--;                           //3.arr[i-1], arr[j] 교환         int temp = arr[i-1];         arr[i-1]=arr[j];         arr[j]=temp;                           int k=N-1;         //4.i부터 N-1까지 오름차순으로 교환         while(i<k) {             temp=arr[i];             arr[i]=arr[k];             arr[k]=temp;             i++;k--;         }                  return true;     } }   http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

package online.base;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main_bj_10974_모든순열_2 {
    static int[] arr;
    static int[] result;
    static boolean[] visit;
    static int N;
    static StringBuilder sb;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        
        N=Integer.parseInt(br.readLine());
        arr=new int[N];
        for(int i=0;i<N;i++) {
            arr[i]=i+1;
        }
        
        result=new int[N];
        visit=new boolean[N];
        sb=new StringBuilder();
//        perm(0);
        
        do {
            for(int n : arr) {
                sb.append(n+" ");
            }
            sb.append("\n");
        }while(nextPermutation());
        
        System.out.print(sb.toString());
    }
    
    
    static boolean nextPermutation() {
        
        //1.부호가 <되는 곳 찾기
        int i=N-1;
        while(i>0 && arr[i-1]>= arr[i])
            i--;
        
        if(i==0)
            return false;
        
        //2.i-1보다 큰 j찾기
        int j=N-1;
        while(arr[i-1]>=arr[j])
            j--;
        
        //3.i-1과 j교환
        int temp=arr[i-1];
        arr[i-1]=arr[j];
        arr[j]=temp;
        
        //4.i부터 N-1까지 교환
        int k=N-1;
        while(i<k) {
            temp=arr[i];
            arr[i]=arr[k];
            arr[k]=temp;
            i++;k--;
        }
        
        
        return true;
    }
    
    static void perm(int depth) {
        if(depth==N) {
            for(int n : result) {
                sb.append(n+" ");
            }
            sb.append("\n");
//            System.out.println(Arrays.toString(result));
            return;
        }
        
        for(int i=0;i<N;i++) {
            if(visit[i]==false) {
                visit[i]=true;
                result[depth]=arr[i];
                perm(depth+1);
                visit[i]=false;
            }
        }
        
    }
}