LinkedHashSet에 대해서

백준의 15663번을 풀며 정리

LinkedHashSet

• 삽입 순서를 보장한다.
• 중복을 허용하지 않는다.
• 삽읍 순서를 보장하는 것 외에는 HashSet과 똑같다.

따라서 중복을 허용하지 않고 순서를 보장해야할 때 사용하는 자료구조가 LinkedHashSet이다.

백준의 15663번에서 LinkedHashSet을 사용하여 문제를 풀 수 있다.

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

import java.util.*;
import java.io.*;

public class Main{

    static int[] arr ;

    static int[] input;

    static int[] visit;

    static LinkedHashSet<String> ans;




    static int N;
    static int M;



    static void DFS(int depth){
        if(depth==M){
            String output = "";
                for(int x: arr){
                    output+=Integer.toString(x)+" ";
                }
                ans.add(output);

        }else{
            for(int i=0;i<N;i++){
                if(visit[i]==0) {
                    visit[i]=1;
                    arr[depth] = input[i];
                    DFS( depth + 1);
                    visit[i]=0;
                }
            }


        }


    }



    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[M];
        visit = new int[N];
        input = new int[N];
        ans = new LinkedHashSet<>();


        Map<Integer,Integer> map = new HashMap<>();

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

        for(int i=0;i<N;i++){
            int x =Integer.parseInt(st.nextToken());
            input[i]=x;
        }



        Arrays.sort(input);


        DFS(0);

        for(String x : ans){
            bw.write(x);
            bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();

    }

}