백준 10974 모든 순열 Java

--> 2019. 6. 12 수정

n이 입력으로 주어지면 

모든 순열을 출력하면 되는 문제이다.

 

다음 순열을 계속해서 구하는 방법과

백트래킹을 사용해서 구하는 방법

두 가지 방법을 알아보자.

 

먼저 순열을 사용한 방법이다.

크기가 n인 배열의 순열의 개수는 n!이다.

n! 만큼 다음 순열을 구한 다음 계속 출력해주면 되는 문제이다.

다음 순열을 구하는 방법을 까먹었다면

https://dundung.tistory.com/58

백준 10972 이전 수열 & 10973 다음 수열 Java

이 글을 보도록 하자.

 

다음 순열을 구하는 메소드의 수행시간은 O(n)이다.

길이가 n인 배열의 순열의 개수는 n!이므로

모든 순열을 구하는 수행시간은 O(n!*n)이다

 

모든 순열을 구할 땐 do while문을 사용하는 것이 가장 올바른 방법이다.

알고리즘 문제를 풀 때 do while을 잘 사용하지 않는데

다음 순열을 구할 땐 가장 많이 사용한다.

 

다음 순열을 구하는 메소드는 이전 글과 똑같고 메인메소드만 조금 다르다.

import java.util.Scanner;
 
public class Q10974 {
 
    static void swap(int [] a , int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    static boolean nextPermutation(int [] a) {
        int i = a.length-1;
        
        while(i > 0 && a[i] <= a[i-1]) {
            i--;
        }
        
        if(i <= 0) {
            return false;
        }
        
        int j = a.length-1;
        while(a[i-1] >= a[j]) {
            j--;
        }
        
        swap(a, i-1, j);
        
        j = a.length-1;
        while(i < j) {
            swap(a, i, j);
            i++;
            j--;
        }
        
        return true;
    }
    
    public static void main(String [] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] a = new int[n];
        
        for(int i=1; i<=n; i++) {
            a[i-1] = i;
        }
        
        do {
            for(int i=0; i<n; i++) {
                System.out.print(a[i]+" ");
            }
            System.out.println();
        } while(nextPermutation(a));
    }
}

 

이번엔 백트래킹으로 구하는 방법이다.

백트래킹은 내가 이해한 바로는

마지막 것을 지워줌으로써 재귀 호출로 되추적을 하는 방식이다.

 

https://www.youtube.com/watch?v=wxQmnEKNXAM

이 동영상에서 굉장히 자세하고 친절하게 백트래킹으로 모든 순열을 구하는 방법을 설명해준다.

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Q10974_ver2 {
    public static void backtrack(List<List<Integer>> list, List<Integer> tmp, int [] nums) {
        if(tmp.size()==nums.length) {
            list.add(new ArrayList<>(tmp));
            return;
        }
        for(int num : nums) {
            if(!tmp.contains(num)){
                tmp.add(num);
                backtrack(list, tmp, nums);
                tmp.remove(tmp.size()-1);
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] nums = new int[n];
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        for(int i=1; i<=n; i++) {
            nums[i-1] = i;
        }
        backtrack(list, tmp, nums);
        for(List<Integer> k : list) {
            for(int i=0; i<n; i++) {
                System.out.print(k.get(i)+" ");
            }
            System.out.println();
        }
    }
}

 

백트래킹 코드가 훨씬 간단하다는 것을 알 수 있다.

시간은 순열이 조금 더 빠른 것 같다.