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

출력

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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
	//freopen("test.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;

	vector<int> vec(n);

	for (int i = 0; i < n; i++)
		cin >> vec[i];

	sort(vec.begin(), vec.end());

	map<string, bool> m;
	int count = 0;
	do {
		string str = "";
		for (int i = 0; i < k; i++)
			str = str + to_string(vec[i]);

		//map에서 특정 키가 있는지 확인하려면 count 함수를 사용하면 된다.
		if (!m.count(str))
		{
			m[str] = true;
			count++;
		}

	} while (next_permutation(vec.begin(), vec.end()));
	
	cout << count;
	return 0;
}

조합순열을 생각하다가 next_permutation이 있다는 걸 찾았다.
map에서 count 함수를 사용하면 찾는 key를 가진 원소의 개수를 출력해주는데 map은 중복을 허용하지 않으므로 0 또는 1을 return 한다는 성질을 이용하여 풀었다.

참조 : https://pearlcrum.tistory.com/entry/BaekJoon-5568%EB%B2%88-%EC%B9%B4%EB%93%9C-%EB%86%93%EA%B8%B0C