[백준](Java) 15655 - N과 M(6)

문제 링크

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

문제 풀이

dfs 뼈대 문제에 중복되는 숫자 조합이 없어야 하는 문제 였다.
ex) 1 7 이 등장한 경우 7 1은 (x)

n,m의 범위가 크지 않아
idx == m 인 경우에
chk의 원소들을 이어서 하나의 String으로 만들어
Map의 key로 만든다.
ex) 1 2 3 4 중에 1 3의 key는 truefalsetruefalse가 될것이고
3 1의 key값도 truefalsetruefalse가 되기 때문에 순서 상관없이 같은 key로 만들 수 있다.

            String key = "";
            for(int i=0; i<chk.length; i++){
                key+=chk[i]+"";
            }

만약에 map에 해당 key가 없는 경우에 해당 결과값을 출력하고
map에 key값을 넣어줘 같은 숫자 조합은 출력하지 않도록 한다.

if(!chkmap.containsKey(key)){
                for (int i = 0; i < m; i++) {
                    System.out.print(list[i] + " ");
                }
                System.out.println("");
                chkmap.put(key,0);
                return;
            }

코드

import java.util.*;


public class Main {

    static int n;
    static int m;
    static int[] arr;
    static boolean[] chk;
    static int[] list;
    static Map<String, Integer> chkmap = new HashMap<>();

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n];
        chk = new boolean[n];
        list = new int[m];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        dfs(0);
    }

    public static void dfs(int idx) {

        if (idx == m) {
            String key = "";
            for(int i=0; i<chk.length; i++){
                key+=chk[i]+"";
            }

            if(!chkmap.containsKey(key)){
                for (int i = 0; i < m; i++) {
                    System.out.print(list[i] + " ");
                }
                System.out.println("");
                chkmap.put(key,0);
                return;
            }
            return;
        }


        for (int i = 0; i < n; i++) {
            if (chk[i]) {
                continue;
            }
            list[idx] = arr[i];
            chk[i] = true;
            dfs(idx + 1);
            chk[i] = false;
        }
    }
}