백준 - 15664 - N과 M(10)

www.acmicpc.net/problem/15664

15664번: N과 M (10)

import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * 백준 15664
 * 순열
 */
public class N과_M_10 {
    private static int N;
    private static int[] array;
    private static boolean[] isUsed;
    private static Set<String> set = new LinkedHashSet<>();

    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];
        isUsed = 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, "", 1);
        for (String str : set) {
            System.out.println(str);
        }
    }

    private static void printPermutation(int M, String str, int start) {
        if(M == 0) {
            set.add(str.trim());
            return;
        }

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

문제

• 주어진 배열에서 위치 중복은 없는 비내림차순 순열
• 위치 중복이 없는 순열이란,, 자기 자신을 중복적으로 결과에 포함시킬 수 없으나
• 같은 데이터라도 자신의 위치가 아닌 다른 위치에 있는 데이터는 다른 데이터로 보고 결과에 포함시킬 수 있음.
• 하지만 결과는 중복될 수 없다.

 

알고리즘

• 백트래킹, 순열
• 자신 중복 체크를 한다
• 결과 중복 체크를 위해 LinkedHashSet을 이용하였다. 중복을 제거해주고 순서를 유지시켜주는 자료구조.