백준 [15663] N과 M (9)

15663번: N과 M (9)

 

처음 풀이 

 

입력에 같은 숫자가 여러번 입력이 주어질 때 중복되는 수열을 걸러내기 위해 Set을 사용했다. 출력 시 사전 순으로 출력하기 위해 Set을 LinkedHashSet으로 선언해주었다.

 

코드

package com.baekjoon.p15663;

import java.util.*;

public class Main {
    static int N, M;
    static Set<String> ans = new LinkedHashSet<>();
    static int[] a, result;
    static boolean[] v;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        a = new int[N];
        result = new int[M];
        v = new boolean[N];

        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
        }

        Arrays.sort(a);

        dfs(0);

        StringBuilder sb = new StringBuilder();
        Iterator<String> it = ans.iterator();
        while (it.hasNext()) {
            sb.append(it.next());
        }
        System.out.println(sb);
        sc.close();
    }

    static void dfs(int depth) {

        if (depth == M) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < M; i++) {
                sb.append(result[i] + " ");
            }
            sb.append("\n");

            ans.add(sb.toString());
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!v[i]) {
                v[i] = true;
                result[depth] = a[i];
                dfs(depth + 1);
                v[i] = false;
            }
        }
    }
}

 

 

다른 풀이

내가 현재 뽑은 값이 이전에 뽑은 값과 같은지 비교할 before 변수를 선언해줬다.

이렇게 되면 인덱스 값만 다른 동일한 값을 가지고 만드는 중복되는 수열을 만들지 않게 된다.

package com.baekjoon.p15663;

import java.util.*;

public class Main {
    static int N, M;
    static Set<String> ans = new LinkedHashSet<>();
    static int[] a, result;
    static boolean[] v;

    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        a = new int[N];
        result = new int[M];
        v = new boolean[N];

        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
        }

        Arrays.sort(a);

        dfs(0);

        System.out.println(sb);
        sc.close();
    }

    static void dfs(int depth) {

        if (depth == M) {
            // StringBuilder sb = new StringBuilder();
            for (int i = 0; i < M; i++) {
                sb.append(result[i] + " ");
            }
            sb.append("\n");
            return;
        }

        int before = 0;

        for (int i = 0; i < N; i++) {
            if (!v[i]) {
                if (before != a[i]) {
                    v[i] = true;
                    result[depth] = a[i];
                    before = a[i];
                    dfs(depth + 1);
                    v[i] = false;
                }
            }
        }
    }
}