백준 - 15654 - N과 M(5)

www.acmicpc.net/problem/15654

15654번: N과 M (5)

import java.util.Arrays;
import java.util.Scanner;

/**
 * 백준 15654
 * 순열
 */
public class N과_M_5 {
    private static int N;
    private static StringBuilder sb = new StringBuilder();
    private static int[] array;
    private static boolean[] isVisit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] inputs = sc.nextLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        int M = Integer.parseInt(inputs[1]);
        array = new int[N+1];
        isVisit = new boolean[N+1];
        String[] nums = sc.nextLine().split(" ");
        for(int i=1; i<=N; i++) {
            array[i] = Integer.parseInt(nums[i-1]);
        }
        Arrays.sort(array);
        printPermutation(M, "");
        System.out.println(sb);
    }

    private static void printPermutation(int M, String str) {
        if(M == 0) {
            sb.append(str.trim() + "\n");
            return;
        }

        for(int i=1; i<array.length; i++) {
            if(!isVisit[i]) {
                isVisit[i] = true;
                printPermutation(M - 1, str + " " + array[i]);
                isVisit[i] = false;
            }
        }
    }
}

문제

주어진 배열에 대한 중복 요소가 없는 순열

 

알고리즘

• 백트래킹, 순열
• 주어진 배열을 사전순으로 출력하기 위해 선작업으로 오름차순 정렬을 해준다