BaekJoon 5568번: 카드 놓기(C++)

www.acmicpc.net/problem/5568

5568번: 카드 놓기

해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.

 

풀이법

1) next_permutation과 map 자료형을 이용하여 푼다면 쉽게 풀 수 있는 문제이다.

2) next_permutation은 현재보다 큰 순열을 만들어 주기 때문에 초기 입력 값에 sort는 필수적이다.

3) map 자료형의 key는 중복이 될 수 없다. 이를 이용하여 문제를 해결했다. 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
int n, k;
int answerNum=0;
vector<int> vec;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		vec.push_back(a);
	}
	sort(vec.begin(), vec.end());
	map<string, bool> m;
	do {
		string s;
		for (int i = 0; i < k; i++)
		{
			s = s + to_string(vec[i]);
		}
		if (m.count(s) == false)
		{
			m[s] = true;
			answerNum++;
		}


	} while (next_permutation(vec.begin(), vec.end()));
	cout << answerNum;
}