[BOJ] 15664번 N과 M(10) (C++)

풀이 소요시간 : 15분

직전에 풀이한 N과 M(9) 문제와 거의 유사한 문제지만 Set 을 이용한 중복체크를 사용했다는 점에서 풀이 방식이 달라 이를 기록하려고 한다.

vector<int> Vector;
set<vector<int>> Set;

위의 Vector 는 수열의 원소를 저장하는 벡터고, Set 는 vector<int> 자료형을 저장할 세트다. 세트의 특성을 이용하여 원소가 같은 벡터마저도 중복체크를 할 수 있다는 점을 알게되었다.

솔직히 앞서 포스팅한 N과 M(9) 의 문제의 아이디어를 떠올리기 쉽지 않다. 하지만 이렇게 기본적인 세트의 특성을 알고있다면 아이디어 발상이 필요없이 직관적인 문제풀이가 가능하다.

전체 코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
using namespace std;

int N, M;
int Map[9];
int Visit[9];
vector<int> Vector;
set<vector<int>> Set;


void Input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> Map[i];
	}
}

void Dfs(int count, int index) {
	if (count == M) {
		Set.insert(Vector);
		return;
	}

	for (int i = index; i <= N; i++) {
		if (Visit[i] == 1) continue;
		Visit[i] = 1;
		Vector.push_back(Map[i]);

		Dfs(count + 1, i);

		Visit[i] = 0;
		Vector.pop_back();
	}
}

int main() {
	Input();
	sort(Map + 1, Map + 1 + N);
	Dfs(0, 1);
	for (auto vector : Set) {
		for (auto element : vector) {
			cout << element << ' ';
		}
		cout << '\n';
	}
}