[백준15663] N과 M (9) (C++)

📌 문제

BOJ 바로가기

주어진 N개의 숫자 중 M개를 사전순 순열로 출력하는 문제이다. 근데 이제 숫자가 중복으로 주어져도 수열은 중복 없이 출력해야 하는...

🗡 풀이

지금까지 풀었던 N과 M 중 제일 어렵다. 중복된 수열을 출력하면 안되기 때문이다.

📍 set이라는 편리한 도구가 있어서 나름 편하게 풀 수 있었다!

📍 처음에는 숫자를 고를 때마다 ans 벡터에 바로바로 push해줬는데 이렇게 하니까 return 될 때마다 ans 벡터가 초기화되는 탓에 문제가 발생하는 듯했다. 그래서 tmp배열을 선언해서 거기에 숫자를 담아주고, 나중에 한꺼번에 벡터에 넣는 식으로 코드를 짰다.

🚩 소스코드

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

int n, m, num[8], tmp[8];
bool visited[8] = { false };
vector<int> ans;
set<vector<int>> s;

void go(int idx) {
	if (idx == m) {
		for (int i = 0; i < m; i++)
			ans.push_back(tmp[i]);
		s.insert(ans);
		ans.clear();
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			tmp[idx] = num[i];
			go(idx + 1);
			visited[i] = false;
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	sort(num, num + n);
	go(0);
	for (auto i : s) {
		for (auto j : i)
			cout << j << " ";
		cout << "\n";
	}
}