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

🔗 문제 링크

BOJ 15663번: N과 M (9)

15663번: N과 M (9)

 

📝 풀이 과정

permutation을 활용해 수열을 구하는 문제이다. 사전순으로 출력하기 위해 Arrays.sort를 활용해 입력이 들어온 숫자들을 오름차순 정렬해주었고, visit배열을 통해 같은 숫자가 수열에 포함되지 않도록 했다.

 

 

input
3 1
4 4 2
--------
output
2
4

이전의 N과 M 문제들과 다른 점은 중복되는 수열이 출력되면 안된다는 점이다.

모든 수열을 구하게 되면 2,4,4가 출력이 되어야하는데 4는 중복되었기 때문에 한 번만 출력을 해야되는 것이다.

 

중복을 처리하는 방법을 고민하던 중 출력값을 String으로 변경해 Set에 넣어 중복을 제거하기로 했다. 오름차순 정렬은 이미 입력을 받아 진행했기 때문에 입력된 순서대로 정렬하는 LinkedHashSet을 활용해 중복을 제거하여 답을 출력하였다

 

 

💡 LinkedHashSet이 아닌 TreeSet을 사용하면 안되는 이유

둘 다 정렬이 가능한 Set이라는 점은 동일하지만 LinkedHashSet은 입력순으로 정렬되고, TreeSet은 생성시 인자로 Comparator를 넘겨주지 않는다면 기본적으로 오름차순 정렬한다.

따라서, TreeSet을 사용하면 String을 기준으로 오름차순 정렬하기 때문에 기존에 숫자가 작은순으로 오름차순 정렬했던 순서가 깨지게 된다.
ex) "16", "135" → "135", "16"

 

💻 코드

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

public class Main {
    static int N, M;
    static int[] nums, perm;
    static boolean[] visit;
    static LinkedHashSet<String> ans;

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

        nums = new int[N];
        perm = new int[M];
        visit = new boolean[N];
        ans = new LinkedHashSet<>();

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

        Arrays.sort(nums);
        permutation(0);
        ans.forEach(System.out::println);
    }

    static void permutation(int cnt) {
        if (cnt == M) {
            StringBuilder sb = new StringBuilder();
            for (int p : perm)
                sb.append(p).append(' ');
            ans.add(sb.toString());
            return;
        }

        for (int i = 0; i < N; i++) {
            if (visit[i])
                continue;
            visit[i] = true;
            perm[cnt] = nums[i];
            permutation(cnt + 1);
            visit[i] = false;
        }
    }
}

 

📊 제출 결과