출처 : https://www.acmicpc.net/problem/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개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.
💻 입력/출력
📝 풀이
본 문제의 설명은 재귀 카테고리에 있는 문제이며, 내가 생각하는 문제의 요점은
바로 중복이 허용 된다는 것이다. 즉 5개의 카드 {1,1,2,3,4} 에서 3개를 뽑는다고 하면 [1,1,2],[1,2,1]
이런식으로 순서가 바뀌어도 해당 값은 정수가 만들어지기 때문에 허용이 된다. 또한 한 개의 정수가 만들어진다 하더라도 그 방법은 다양할수도 있기 때문에 그런 중복은 허용이 되지 않는다 즉, 정수의 갯수만 파악하여야 한다.
위 문제를 풀기 위해선 가장 먼저 정수가 어떤 방식으로 만들어질지 생각해봐야 한다.
위와 같은 예시에서 3개의 카드를 뽑는 경우의 수는
[1,1,2][1,1,3] [1,1,4][1,2,3] [1,2,4][1,2,1] [1,3,4][1,3,1] [1,3,2] ···
이런식으로 진행되게 된다. 이러한 패턴을 파악하기 쉽게 구성한다면
1
1
2 [1,1,2]
3 [1,1,3]
4 [1,1,4]
2
3 [1,2,3]
4 [1,2,4]
1 [1,2,1]
3
4 [1,3,4]
1 [1,3,1]
2 [1,3,2]
4
1 [1,4,1]
2 [1,4,2]
3 [1,4,3]
2
·
·
·
·
·각 정수의 자릿수를 level[0,1,2] 라고 한다면
0 level의 반복수는 n번
1 level은 n-1번
2 level은 n-2번이다.
우리는 n=5인 경우를 살펴봤으니, 세 단계에서 각각 5번 4번 3번을 반복하여 정수를 추출해내는 것이다. 그리고 재귀 함수 맨 앞에 level이 1의 자리 정수를 구할 때, String으로 해당 정수를 추가시켜서 ArrayList.contains() 메소드를 통해 있는 지 확인한 수 false라면 해당 정수를 추가시킨다.
내가 제시한 기준에서 나는 10의 자리수가 바뀌는 과정을 배열의 재조정을 통해 풀었다.
코드를 통해 알아보자
📋 코드
public class card {
static int k = 0;
static int n = 0;
static ArrayList<String> jungsuList = new ArrayList<String>();
public static void main(String[] args) throws NumberFormatException, IOException {
ArrayList<Integer> arr = new ArrayList<Integer>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
k = Integer.parseInt(br.readLine());
for (int q=0; q<n; q++) {
arr.add(Integer.parseInt(br.readLine()));
}
pushBlock(arr,"",0);
System.out.println(jungsuList.size());
}
public static void pushBlock(ArrayList<Integer> a,String number, int count) {
String abc = number;
if (count == k-1) {
for (int k=count; k<n; k++) {
number += String.valueOf(a.get(k));
if (!jungsuList.contains(number)) { // arraylist에 같은 수가 있는지 확인
jungsuList.add(number);
}
number = abc;
}
return;
}
for (int i=count; i<n; i++) {
number += String.valueOf(a.get(count));
pushBlock(a,number,count+1);
int temp = a.get(count);
a.remove(count);
a.add(temp);
number = abc;
}
}
}
