순열, 조합, 중복순열, 중복조합 정리

순열

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

public class 순열 {
    static int N, M;
    static boolean[] isVisited;
    static int[] permutation;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        isVisited = new boolean[N + 1];
        permutation = new int[M];
        getPermutation(0);
        System.out.println(sb);
    }
    public static void getPermutation(int depth) {
        if (depth == M) {
            for (int i = 0; i < permutation.length; i++) {
                sb.append(permutation[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 1; i <= N; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                permutation[depth] = i;
                getPermutation(depth + 1);
                isVisited[i] = false;
            }
        }
    }
}

조합

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

public class 조합 {
    static int N,M;
    static boolean[] isVisited;
    static int[] combination;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        isVisited = new boolean[N + 1];
        combination = new int[M + 1];
        getCombination(0);
        System.out.println(sb);
    }

    public static void getCombination(int depth) {
        if (depth == M) {
            for (int i = 1; i < combination.length; i++) {
                sb.append(combination[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 1; i <= N; i++) {
            if (!isVisited[i] && combination[depth] < i) {
                isVisited[i] = true;
                combination[depth + 1] = i;
                getCombination(depth + 1);
                isVisited[i] = false;
            }
        }
    }
}

중복순열

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

public class 중복순열 {
    static int N, M;
    static int[] repeatedPermutation;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        repeatedPermutation = new int[M];
        getRepeatedPermutation(0);
        System.out.println(sb);
    }
    public static void getRepeatedPermutation(int depth) {
        if (depth == M) {
            for (int i = 0; i < repeatedPermutation.length; i++) {
                sb.append(repeatedPermutation[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 1; i <= N; i++) {
            repeatedPermutation[depth] = i;
            getRepeatedPermutation(depth + 1);
        }
    }

}

중복조합

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

public class 중복조합 {
    static int N, M;
    static int[] repeatedCombination;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        repeatedCombination = new int[M + 1];
        getRepeatedCombination(0);
        System.out.println(sb);
    }

    public static void getRepeatedCombination(int depth) {
        if (depth == M) {
            for (int i = 1; i < repeatedCombination.length; i++) {
                sb.append(repeatedCombination[i]).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (repeatedCombination[depth] <= i) {
                repeatedCombination[depth + 1] = i;
                getRepeatedCombination(depth + 1);
            }
        }
    }
}

정리

기본적으로 크게 3가지가 필요하다.
순열과 조합을 돌릴 배열, (방문 여부 체크하는 배열), 결과를 반환할 배열
이때 중복순열, 중복조합은 당연하게도 방문 여부 체크하는 배열이 필요없다.

또한 다음의 2가지 기준으로 나누어 볼 수 있다
1. 순열인지 조합인지
가장 큰 차이는 조합의 경우 추가적으로 이전 값과 비교하는 로직이 필요하다는 것이다. 또한 조합의 경우 비교하는 로직이 있기 때문에 0번 index가 필요하여 1번부터 출력하는 것이 차이이다.

2. 중복이 없는지 있는지
가장 큰 차이는 방문 체크 배열의 필요 여부이다. 중복이 없다면 방문 체크 배열이 필요하지만 중복이 있다면 방문 체크 배열이 필요없다

추가) 코딩테스트에서 순열, 조합, 중복순열, 중복조합 중 1개를 구현한 뒤에 반환된 결과값이 특정 조건을 만족하는지 여부를 판단하도록 자주 출제된다. 따라서 4가지를 빠르게 구현하는 것이 중요하다.