링크

15663 N과 M(9)

문제

풀이

푸는데 오래걸렸다. 중복을 제거하고 순서도 유지해야하기 때문에 set중에 LinkedHashSet이라는 것을 사용하자

푸는 방법은
1. 정렬한다
2. 백트래킹을 통해서 list에다가 요소 하나하나 넣고 완성된 경우 set에 넣는다(이때 나는 공백도 추가해서 넣어줬따)
3. 그리고 요소 하나하나 꺼내서 출력하면 끝

정리해보면서 적으니까 은근 쉬운데 왜캐 헤맷는지 모르겠다.

코드

import java.awt.desktop.PreferencesEvent;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    public static List<Integer> list = new ArrayList<>();
    public static boolean[] visited;
    public static int[] array;
    public static Set<String> LinkedSet = new LinkedHashSet<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);

        visited = new boolean[n];
        array = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0;i<n;i++){
            array[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(array);

        dfs(0, m);

        StringBuffer sb = new StringBuffer();
        Iterator iter = LinkedSet.iterator();
        while(iter.hasNext()){
//             System.out.println(iter.next());
             String str = (String) iter.next();

             for(int i=0;i<str.length();i++) {
                 sb.append(str.charAt(i));
             }

             if(iter.hasNext())
                sb.append("\n");
        }

        System.out.println(sb.toString());

    }

    public static void dfs(int dept, int limit){
        if(dept == limit){
//            System.out.println(list);
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<list.size();i++){
                sb.append(list.get(i) + " ");
            }

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

        for(int i=0;i<array.length;i++){
            if(!visited[i]){
                visited[i] = true;
                list.add(array[i]);
                dfs(dept+1, limit);
                list.remove(list.size() - 1);
                visited[i] = false;
            }
        }


    }
}