[C++] 5568번: 카드 놓기

링크

https://www.acmicpc.net/problem/5568

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

출력

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

예제 입력 1 복사

4
2
1
2
12
1

예제 출력 1 복사

7

예제 입력 2 복사

6
3
72
2
12
7
2
1

예제 출력 2 복사

68

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <cmath>
#include <queue>
#include <stack>

using namespace std;

vector<string> nums;
unordered_set<string> sets;
int answer = 0;
int n, k;

int main(void)
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		string temp;
		cin >> temp;
		nums.push_back(temp);
	}
	
	sort(nums.begin(), nums.end());

	do
	{
		string temp;

		for (int i = 0; i < k; i++)
			temp += nums[i];

		sets.insert(temp);
	} while (next_permutation(nums.begin(), nums.end()));
		
	cout << sets.size() << endl;

	return 0;
}

풀이

• algorithm 해더파일의 next_permutation을 사용해 순열을 구하였다.
  
  
• next_permutation을 이용해 순열을 구하기 위하여 오름차순으로 정렬하였다.
  
  
• set에 저장하기 때문에 중복은 자동으로 처리된다.