[백준][15663번] N과 M (9)

문제 URL

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

첫번째 풀이

import java.util.*;
public class Main {
    static int[] a = new int[10];
    static int[] num = new int[10];
    static int[] cnt = new int[10];
    static void go(int index, int n, int m) {
        if (index == m) {
            for (int i=0; i<m; i++) {
                System.out.print(num[a[i]] + " ");
            }
            System.out.println();
            return;
        }
        for (int i=0; i<n; i++) {
            if (cnt[i] > 0) {
                cnt[i] -= 1;
                a[index] = i;
                go(index+1, n, m);
                cnt[i] += 1;
            }
        }
    }   
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] temp = new int[n];
        for (int i=0; i<n; i++) {
            temp[i] = sc.nextInt();
        }
        Arrays.sort(temp);
        int k = 0;
        int x = temp[0];
        int c = 1;
        for (int i=1; i<n; i++) {
            if (x == temp[i]) {
                c += 1;
            } else {
                num[k] = x;
                cnt[k] = c;
                k += 1;
                x = temp[i];
                c = 1;
            }
        }
        num[k] = x;
        cnt[k] = c;
        n = k+1;
        go(0, n, m);
    }
}

두번째 풀이

import java.util.*;
class Result implements Comparable<Result> {
    Integer[] a;
    Result(ArrayList<Integer> a) {
        this.a = a.toArray(new Integer[a.size()]);
    }
    int get(int index) {
        return (int)this.a[index];
    }
    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Result) {
            Result that = (Result)obj;
            int n = this.a.length;
            for (int i=0; i<n; i++) {
                if (this.a[i] != that.a[i]) {
                    return false;
                }
            }
            return true;
        } else {
            return false;
        }
    }
    public int compareTo(Result that) {
        int n = this.a.length;
        for (int i=0; i<n; i++) {
            if (this.a[i] == that.a[i]) continue;
            if (this.a[i] < that.a[i]) return -1;
            if (this.a[i] > that.a[i]) return 1;
        }
        return 0;
    }
}
public class Main {
    static boolean[] c = new boolean[10];
    static int[] a = new int[10];
    static int[] num = new int[10];
    static ArrayList<Result> d = new ArrayList<>();
    static void go(int index, int n, int m) {
        if (index == m) {
            ArrayList<Integer> temp = new ArrayList<>();
            for (int i=0; i<m; i++) {
                temp.add(num[a[i]]);
            }
            d.add(new Result(temp));
            return;
        }
        for (int i=0; i<n; i++) {
            if (c[i]) continue;
            c[i] = true;
            a[index] = i;
            go(index+1, n, m);
            c[i] = false;
        }
    }   
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for (int i=0; i<n; i++) {
            num[i] = sc.nextInt();
        }
        Arrays.sort(num, 0, n);
        go(0, n, m);
        Collections.sort(d);
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<d.size(); i++) {
            if (i == 0 || !d.get(i).equals(d.get(i-1))) {
                for (int j=0; j<m; j++) {
                    sb.append(d.get(i).get(j));
                    if (j != m-1) sb.append(' ');
                }
                sb.append('\n');
            }
        }
        System.out.print(sb);
    }
}

느낀점

N개의 자연수 중에서 M개를 고른 수열을 모두 구하는 문제

• 첫번째풀이 각 숫자가 얼마나 중복되는지 미리 count하고 계산하는방법

• 두번째풀이 모든 수열을 구한다음, 중복을 제거하는 방식으로 풀 수 있다. n과 m(5) 문제풀이 + 중복제거 추가