백준 N과 M (2)_15650

⭐문제링크

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int M;
    static boolean visit [];
    static int array[];
    static Set<String> check = new HashSet<>();
    static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        visit = new boolean[N];
        array = new int[M];

        dfs(0);
        System.out.println(answer);
    }

    public static void dfs(int depth) {

        if (depth == M) {
            // StringBuilder 객체를 생성하여 현재 수열(array)의 값을 문자열로 변환
            StringBuilder sb = new StringBuilder();
            for (int val : array) {
                sb.append(val).append(" ");
            }
            // forward는 현재 수열을 문자열로 나타낸 것
            //.trim() 은 공백 제거용 함수이다.
            String forward = sb.toString().trim();

            // 현재 수열(array)의 복사본을 만들고 이를 정렬
            int[] sortedArray = array.clone();
            Arrays.sort(sortedArray);

            // sortedArray를 문자열로 변환하여 sortedKey에 저장
            String sortedKey = Arrays.toString(sortedArray);

            // check 셋에 sortedKey가 이미 존재하는지 확인
            if (check.contains(sortedKey)) return;

            // check 셋에 sortedKey 추가 (중복 수열 제거를 위해)
            check.add(sortedKey);

            // 정렬되지 않은 원래 수열을 answer에 추가
            answer.append(forward).append("\n");
            return;
        }

        for(int i=0; i<N; i++) {
            if(!visit[i]) {
                visit[i]=true;

                array[depth] = i+1;
                dfs(depth+1);

                visit[i]=false;
            }
        }
    }

}

원래 이런식으로 짰었는데 굉장히 비효율적이 코드였다.
그래서 다른 사람들 코드를 보니 굉장히 놀랐다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int M;
    static boolean visit [];
    static int array[];

    static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        visit = new boolean[N];
        array = new int[M];

        dfs(0,0);
        System.out.println(answer);
    }

    public static void dfs(int start, int depth) {
        if(depth==M) {
            for(int val : array){
                answer.append(val+" ");
            }
            answer.append("\n");
            return;
        }

        for(int i=start; i<N; i++) {
            if(!visit[i]) {
                visit[i]=true;

                array[depth] = i+1;
                dfs(i+1, depth+1);

                visit[i]=false;
            }
        }
    }

}

위와 같이 인자 하나를 바꾸는 것으로 아주 간편하게 중복을 제거할 수 있었다. N과 M은 수열 배우는 데엔 최고인 거 같다.