순열(Permutation)

• n개의 값 중에서 r 개의 숫자를 순서를 고려해 나열한 경우의 수

  [1, 2, 3] 이라는 3 개의 배열에서 2 개의 숫자를 뽑는 경우는 6개임
  
  [1, 2][1, 3]
  [2, 1][2, 3]
  [3, 1][3, 2]

• 구현에는 2가지 방법이 있음

  1. Swap을 이용한 순열 (다음 수열)
  2. Visited 배열을 이용한 순열 (DFS)

• 시간 복잡도: O(n!)

Swap을 이용한 순열

다음 순열(Next Permutation)

• 순열 및 조합을 생성할 때 재귀적으로 구현하지 않고, 각 인덱스 값을 비교하여 모든 경우의 인덱스 값을 뽑아내는 방법

• 과정

  1. 순열을 사전순(오름차순)으로 생성
  2. 가장 작은 값부터 가장 큰 값이 될 때 까지 한 자리씩 swap하며 출력(내림차순)

장점

• 재귀로 짜여진 순열보다 시간 복잡도 낮음
• 순열과 조합 함께 사용 가능

단점

• 원래의 배열을 오름차순으로 재배열하여 순열을 만들어내기 때문에 특정 개수의 순열을 만들어낼 수 없음

알고리즘

배열을 오름차순의 순열로 만들어놓고 시작해 아래 과정을 반복
ex) 1, 2, 3, 4, 5, 6, 7, ... , i

1. 뒤 쪽부터 탐색하여 교환할 위치(i-1) 찾기
   • 가장 뒤 쪽(arr.length-1)부터 가장 큰 수인 i부터 탐색해 i-1 > i인 경우 i--를 하며 i-1 < i까지 반복 탐색
   • i = 0인 경우 마지막 순열(내림차순 순열)까지 탐색 완료
2. 뒤 쪽부터 탐색하여 교환할 위치(i-1)의 값 보다 큰 값의 위치(j) 찾기
   • 가장 뒤 쪽(arr.length-1)부터 가장 큰 수인 j부터 탐색해 i-1 > j인 경우 j--를 하며 i-1 < j까지 반복 탐색
3. i-1과 j의 값 교환
   • swap(i-1, j)
4. 가장 큰 값인 i 이후의 값들은 다시 오름차순 정렬

코드

💡 관련 문제:백준 10972 다음 수열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        if (check()) {
            for (int i = 0; i < N; i++)
                System.out.print(arr[i] + " ");
        } else
            System.out.println(-1);
    }

    static boolean check() {
        // 1. 가장 뒤 쪽(i)부터 i-1 < i이 성립될 때 까지 i-- 하며 탐색해 교환할 위치(i-1) 찾기
        int i = arr.length - 1;
        while (i > 0 && arr[i-1] > arr[i])
            i--;
        if (i <= 0)
            return false;

        // 2. 가장 뒤 쪽(j)부터 i-1 < j이 성립될 때 까지 j-- 하며 탐색해 i-1와 교환할 j 찾기
        int j = arr.length - 1;
        while (arr[i-1] > arr[j])
            j--;

        // 3. i-1과 j의 값 교환
        swap(i-1, j);

        // 4. 가장 큰 값인 i부터 가장 마지막 값인 j까지 다시 오름차순 정렬
        j = arr.length-1;
        while (i < j) {
            swap(i, j);
            i++;
            j--;
        }
        return true;
    }

    static void swap(int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

Visited 배열을 이용한 순열

DFS

• 순열 및 조합을 생성할 때 재귀적으로 구현하여, 모든 경우의 인덱스 값을 뽑아내는 방법
• 과정
  1. arr 배열에 담긴 N개의 정수를 visited 변수를 사용해 DFS로 arr 배열의 모든 인덱스에 방문
  2. 아직 방문하지 않은 인덱스는 res 배열에 넣음
     이 때, depth는 1씩 늘림
  3. depth가 N과 같아질 때까지 반복

장점

• 시간복잡도가 Swap을 이용한 구현보다 빠름

코드

👉 관련 문제: 백준 10819 차이를 최대로

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] arr, res;
    static boolean[] visited;
    static int sum, result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];  // 입력받을 배열
        res = new int[N];  // 탐색하며 새로 생성할 배열
        visited = new boolean[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        dfs(0);
        System.out.println(result);
    }

    static void dfs(int depth) {
        if (depth == arr.length) {
            sum = 0;

            for (int i = 0; i < res.length; i++) {
                System.out.print(res[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                res[depth] = arr[i];
                dfs(depth+1);
                visited[i] = false;
            }
        }
    }
}