[BOJ]10974번 : 모든 순열

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

10974번: 모든 순열

분류 : 순열 

import java.io.*;
import java.math.*;
import java.util.*;

class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    char nextChar() {
        return next().charAt(0);
    }
}

public class Main
{
    static StringBuilder sb = new StringBuilder();
    public static PrintWriter out;
    static int N;
    public static void main(String[] args) throws IOException
    {
        MyScanner sc = new MyScanner();
        N = sc.nextInt();
        int[] arr = new int[N];
        for(int i=0;i<N;i++)
        {
            arr[i] = i+1;
            sb.append(i+1+" ");
        }
        sb.append("\n");
        
        while(nextPermutation(arr)){}
            System.out.println(sb.toString());
    }
    private static boolean nextPermutation(int[] arr)
    {
        int index1 = arr.length-1;
        while(index1>0 && arr[index1-1]>=arr[index1]){
            index1--;
        }
        if(index1<=0)
            return false;
        int index2 = arr.length-1;
        while(arr[index2]<=arr[index1-1]){
            index2--;
        }
        
        int tmp = arr[index1-1];
        arr[index1-1]= arr[index2];
        arr[index2] = tmp;
        
        index2 = arr.length-1;
        while(index1<index2){
            tmp=arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = tmp;
            index1++;
            index2--;
        }
        
        Print(arr);
        return true;
    }
    private static void Print(int[] arr) {
        for(int i=0;i<N;i++){
            sb.append(arr[i]+" ");
        }
            sb.append("\n");        
    }
}

문제만 읽으면 정말 단순한 문제 모든 순열 만들어서 출력하는 문제..

C++에서는 nextPermutation 함수를 이용하면 쉽게 풀린다고 한다.

하지만 자바는 없기에 구글링 해가면서 배웠다..

코드는 http://java7ang.tistory.com/9 에서 주로 참조하였고 마이구미라는 분의 블로그 자료도 보며 코드를 수정했다.

공부가 많이 부족하구나 라는 생각이 자주 든다..

같은 맥락의 문제로는 "10819번 : 차이를 최대로"가 있다.

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