문제 링크

문제

상근이는 카드 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개 줄에는 카드에 적혀있는 수가 주어진다.

출력

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

예제 입력 / 출력

// 예제 입력 1
4
2
1
2
12
1

// 예제 출력 1
7

// 예제 입력 2
6
3
72
2
12
7
2
1

// 예제 출력 2
68

힌트

예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다.

알고리즘
이 문제는 단순한 순열 문제로 해석될 수 있다. 하지만 주의해야 할 점은 2자리 수의 숫자 카드도 존재하기 때문에 다른 수들의 조합이지만 결과적으로 같은 정수를 만들 수도 있다는 점이다. 이 점을 해결하기 위해 <unordered_map> 라이브러리를 사용한다.

우선 재귀함수로 순열을 구하는 permutation함수를 작성한다.
그런 뒤 결과 값을 string으로 바꾸어 map[string]의 값을 증가시켜준다. 예를 들어 1, 2 숫자카드를 순열로 표현하면 12, 21이 나온다. 이것을 map[12] = 1, map[21] = 1 이런식으로 map에 저장하는 방식이다.
여기서 주의해야 할 점은 숫자가 2자리수 카드인 경우에는 십의자리수와 일의 자리수를 각각 string으로 변환시켜주어야 한다는 것이다. (string 라이브러리에 포함되어 있는 to_string함수로도 쉽게 구현 가능)
그리고 마지막으로 map의 size를 출력시켜주면 중복되는 값을 포함하지 않게 처리가 가능하다.

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int n, k;
int card[11];
unordered_map<string, int> m;

void permutation(int depth) {

	if (depth == k) {
		string temp;
		
		for (int i = 0; i < k; i++) {
			if (card[i] < 10) temp += card[i] + '0';
			else {
				temp += (card[i] / 10) + '0';
				temp += (card[i] % 10) + '0';
			}
		}
		m[temp]++;

		return;
	}

	for (int i = depth; i < n; i++) {
		swap(card[depth], card[i]);
		permutation(depth + 1);
		swap(card[depth], card[i]);
	}
}

int main(void) {

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		cin >> card[i];
	}

	permutation(0);
	
	cout << m.size();
}