[240408] 알고리즘 리부트 45일차 - 백준 5568 자바

동일한 숫자는 카운트하지 않기 때문에 set을 활용해야겠다고 판단했다. 숫자를 고르는 방법은 특정 인덱스를 기준으로 뒤의 숫자만 고르게 하려고 했었다. 그런데 이렇게 처리하게되면 뽑은 숫자마다 순서를 직접 달리 배치해봐야 하는 번거로움이 발생한다. 따라서 방문 배열을 생성하고 해당 숫자를 뽑았는지를 체크하며 고르고 모든 인덱스를 순회하도록 처리했다. 이렇게 처리하면 모든 숫자를 순회하는 대신 뽑은 숫자 간의 숫자를 바꿔서 배치할 필요가 없다. k개의 카드만 뽑아야 하므로 cnt 변수로 뽑은 숫자를 관리했다.

package BaekJoon.backtracking;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class BJ5568 {
    private static int n,k;
    private static int pool[];
    private static boolean visited[];
    private static HashSet<String> answer;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        k = sc.nextInt();

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

        for(int i =0; i<n; i++){
            pool[i] = sc.nextInt();
        }

        //System.out.println(Arrays.toString(pool));

        answer = new HashSet<>();
        makeNum("", 0);
        
        System.out.println(answer.size());
    }
    
    private static void makeNum(String num, int cnt){
        StringBuilder sb;
        //System.out.println("cnt는: "+cnt);
        if(cnt == k){
            //System.out.println(num+" 답에 추가");
            answer.add(num);
            return;
        }

        if(cnt<k) { //앞뒤로만 붙여서는 안된다.. -> 본인 숫자 제외하고 조합하기
            for (int i = 0; i < n; i++) {
                if(visited[i]) continue;
                sb = new StringBuilder();
                String tmp1 = sb.append(num).append(pool[i]).toString();
                visited[i] = true;
                //System.out.println("tmp1: "+tmp1);
                makeNum(tmp1, cnt + 1);
                visited[i] = false;
            }
        }
    }
}