기록을

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

숫자의 입력이 중복되어서 들어올 수 있다.

결과로 나오는 수열은 오름차순으로 정렬되는 상태여야 한다. 하지만 입력은 정렬되어서 들어오는 것이 아니기 때문에 입력을 모두 받은 이후에 오름차순 정렬을 해줘야 한다.

또한, 사용했던 숫자를 재사용할 수 있기 때문에 숫자의 사용 중 여부를 판단하는 배열 또한 필요하지 않다.

그리고 수열이 중복되어서 생성될 수 있는데, 이는 중복을 허용하지 않는 set을 활용해서 처리했다.

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int m, n, arr[7], num[7];
set<vector<int > > st;
vector<int> v;
void func(int k) {
	if (k == m) {
		for (int i = 0; i < m; i++) {
			v.push_back(arr[i]);
		}
		st.insert(v);
		v.clear();
		return;
	}
	for (int i = 0; i < n; i++) {
		arr[k] = num[i];
		func(k + 1);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	sort(num, num + 1);
	func(0); //0번까지 채워져있다
	set<vector<int> >::iterator itr;
	for (itr = st.begin(); itr != st.end(); itr++) {
		vector<int> tmp = *itr;
		for (int i = 0; i < tmp.size(); i++)
			cout << tmp[i] << ' ';
		cout << '\n';
	}
	return 0;
}

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

사용할 수 있는 숫자들 중에 중복되는 숫자가 있을 수 있다.

숫자는 중복해서 사용하면 안 되고 입력받은 개수만큼만 사용해야 하며

만들어낸 수열은 비내림차순이어야 한다.

#include<iostream>
#include<vector>
#include<unordered_set>
#include<set>
using namespace std;
int N, M, arr[9], n[9];
bool isused[9];
set<vector<int> > st;
vector<int> v;
void func(int k) {
	
	if (k == M + 1) {
		for (int i = 1; i <= M; i++) {
			v.push_back(arr[i]);
		}
		st.insert(v);
		v.clear();
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (!isused[i] && arr[k - 1] <= n[i]) {
			isused[i] = true;
			arr[k] = n[i];
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> n[i];
	}
	func(1);
	for (set<vector<int> >::iterator it = st.begin(); it != st.end(); it++) {
		for (int i = 0; i < (*it).size(); i++) {
			cout << (*it)[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

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

쉽게 풀려면 쉽게 풀 수 있는 문제이다.

문제를 살펴보자. 먼저 같은 숫자가 여러 번 등장할 수 있다는 조건이 있다.

즉 1 9 9 이런식으로 숫자의 목록이 있다면, 길이 2의 수열이 19 19 91 99 91 99 이렇게 3p2개 나올 수 있다는 것이다.

이제 중복을 제거해줘야 하고, 오름차순으로 정렬을 해줘야 한다.

정렬 방법은, 지금까지 그래 왔던 것처럼 미리 사용 가능 숫자들을 정렬해주면 된다.

또한 중복을 제거할 때는, 여러가지 방법이 물론 있겠지만, 간단하게 중복을 허용하지 않는 set을 사용했다.

set에 어떤 data를 삽입할 때, 이미 같은 데이터가 set 내부에 존재하면, 삽입 시도는 무시된다.

그런데 이번 문제를 풀던 도중 새로운 사실을 알았다.

처음에는 string type으로 공백과 함께 set에 담아서 출력을 하려고 했다.

따라서 set<string> 이렇게 타입을 잡았는데, set 안에 들어가게 되면 string을 나중에 꺼내서 사용할 때 string의 길이가 1이 된다는 것이다. 즉 string이 내가 평소에 아는 string이 아니게 된다.

이 문제를 해결하기 위해 set안에 vector을 넣기로 하고 문제를 해결했다. vector는 이상 없이 작동했다.

#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int n, m, arr[11], num[11];
bool isused[11];
set<vector<int> > ctnr;
void func(int k) {
	if (k == m + 1) {
		vector<int> v;
		for (int i = 1; i <= m; i++) {
			v.push_back(arr[i]);
		}
		ctnr.insert(v);
		v.clear();
		return;
	}
	
	for (int i = 1; i <= n; i++) {
		if (!isused[i]) {
			arr[k] = num[i];
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	sort(num + 1, num + 1 + n);

	func(1);

	/*for (set<string>::iterator i = ctnr.begin(); i != ctnr.end(); i++) {
		for (int j = 0; j < (*i).length(); j++) {
			if (j % 2 == 0) cout << stoi((*i).substr(j, 1));
			else cout << ' ';
		}
		cout << '\n';
	}*/
	for (auto e : ctnr) {
		for (int i = 0; i < e.size(); i++) {
			cout << e[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}