[백준] 5568. 카드 놓기

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

 

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

 

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

---

예제 입력 2

6
3
72
2
12
7
2
1

예제 출력 2

68

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static int n, k;
    public static int[] arr;
    public static int[] selected;
    public static boolean[] visited;
    public static Set<Integer> set;
    public static void main(String[] args) throws Exception {
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        set = new HashSet<>();
        arr = new int[n];
        visited = new boolean[n];
        selected = new int[k];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine()); 
        }

        permutation(0);
        bw.write(Integer.toString(set.size()));
        br.close();
        bw.flush();
        bw.close();
    }

    public static void permutation(int cnt) {
        if(cnt == k) {
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < k; i++) {
                sb.append(Integer.toString(arr[selected[i]]));
            }
            set.add(Integer.parseInt(sb.toString()));
            return;
        }

        for(int i = 0; i < n; i++) {
            if(visited[i]) {
                continue;
            }
            selected[cnt] = i;
            visited[i] = true;
            permutation(cnt + 1);
            visited[i] = false;
        }
    }
}

중복을 거르기 위해 HashSet을 사용하였고 순열을 이용해 경우의 수를 찾아내었다.