상근이는 카드 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개 줄에는 카드에 적혀있는 수가 주어진다.
입력 | 출력 |
---|---|
4 | |
2 | |
1 | |
2 | |
12 | |
1 | 7 |
6 | |
3 | |
72 | |
2 | |
12 | |
7 | |
2 | |
1 | 68 |
Hash 자료 구조로 중복 자연스럽게 제거하고 순열 뽑기 생각
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class four5568 {
private int n;
private int k;
private int[] numbers;
private int[] arr;
private boolean[] visited;
private Map<String, Integer> candidates;
public void solution() throws IOException {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
numbers = new int[n];
visited = new boolean[n];
arr = new int[k];
candidates = new HashMap<>();
for (int i = 0; i < n; i++) {
numbers[i] = sc.nextInt();
}
permutation(0);
System.out.println(candidates.keySet().size());
}
private void permutation(int depth) {
if (depth == k) {
String atrArr = "";
for (int val : arr) {
atrArr += val;
}
if (!candidates.containsKey(atrArr)) {
candidates.put(atrArr, 0);
}
return;
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
arr[depth] = numbers[i];
permutation(depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
new four5568().solution();
}
}