N과 M (5) 15654

https://www.acmicpc.net/problem/15654

import java.io.*;
import java.util.Arrays;

public class Main {

    static int N;
    static int M;

    static int[] inputArr;
    static int[] arr;
    static boolean[] checked;

    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args)throws IOException
    {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input;
        input = br.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        inputArr = new int[N];
        arr = new int[M];
        checked = new boolean[N];

        input = br.readLine().split(" ");
        for(int i = 0; i < N; ++i)
        {
            inputArr[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(inputArr);

        search(0);

        System.out.println(sb);
    }

    static void search(int depth)
    {
        if(depth == M)
        {
            for(int i = 0; i < arr.length; ++i)
            {
                if(i != arr.length-1)
                    sb.append((arr[i]) + " ");
                else
                    sb.append((arr[i]) + "\n");
            }
            return;
        }

        for(int i = 0; i < N; ++i)
        {
            if(checked[i] == false)
            {
                checked[i] = true;
                arr[depth] = inputArr[i];
                search(depth+1);
                checked[i] = false;
            }
        }
    }
}

시간이 지나서 두번째로 풀어봄
근데 숫자 크기로 정렬해서 출력하는 부분에서 막혀서 고민하다가 예전에 어떻게 풀었는지 참고하였다
한참 고민햇는데 답은 입력된 숫자를 정렬한뒤에 배열을 만들면 되는거였다

시간복잡도 O(N^M)

8 8
1 2 3 4 5 6 7 8
입력하고

dfs 함수 에서 count 변수로 몇번호출되는지 돌려보니 109601 나옴

8의8승은 16,777,216 인데 왜 더 적게 숫자가 나왔을까 중복이 제거되서 그런건가?

import java.io.*;
import java.util.*;

public class Main {

    static int N;//1~8
    static int M;//1~8
    static Integer[] arr;
    static ArrayList<String> answer = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        input = br.readLine().split(" ");

        ArrayList<Integer> arrInput = new ArrayList<>();
        for(int i = 0; i < N; ++i){
            arrInput.add(Integer.parseInt(input[i]));
        }

        Collections.sort(arrInput);
        boolean visit[] = new boolean[N];
        arr = new Integer[M];

        dfs(0, arrInput, visit);


        answer.stream().forEach( (s)->{
            System.out.println(s);
        });
    }

    public static void dfs(int depth, ArrayList<Integer> arrInput, boolean visit[]){

        sb.setLength(0);
        if(depth == M){
            for (int i = 0; i < arr.length; ++i) {
                if(i == arr.length - 1)
                    sb.append(arr[i]);
                else
                    sb.append(arr[i] + " ");
            }

            answer.add(sb.toString());

            return;
        }

        for(int i = 0; i < N; ++i){

            if(visit[i] == false){
                arr[depth] = arrInput.get(i);
                visit[i] = true;
                dfs(depth+1, arrInput, visit);
                visit[i] = false;
            }
        }
    }
}