[백준 15664번] N과 M(10) C++ 풀이

시간 제한

1초

메모리 제한

512MB

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수는 모두 다른 수이다.
N개의 자연수 중에서 M개를 고른 수열
고른 수열은 비내림차순이어야 한다.
(길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.)

입력

첫째 줄에 N과 M이 주어진다.(1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

내 맞은 풀이

#include<bits/stdc++.h>
using namespace std;

int n(0), m(0);
int inputSeq[10] = { 0 };
bool isUsed[10] = { 0 };
vector<int> outputSeq;
set<vector<int>> checker;

void makeSeq(int cur, int latestIdx) {
	if (cur == m) {
		checker.insert(outputSeq);
		return;
	}
	for (int i = latestIdx; i < n; i++) {
		if (!isUsed[i]) {
			isUsed[i] = true;
			outputSeq.push_back(inputSeq[i]);
			makeSeq(cur + 1, i + 1);
			isUsed[i] = false;
			outputSeq.pop_back();
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> inputSeq[i];
	sort(inputSeq, inputSeq + n);
	makeSeq(0, 0);
	for (set<vector<int>>::iterator iter1 = checker.begin(); iter1 != checker.end(); iter1++) {
		for (vector<int>::const_iterator iter2 = (*iter1).begin(); iter2 != (*iter1).end(); iter2++) {
			cout << *iter2 << ' ';
		}
		cout << '\n';
	}
	return 0;
}

set와 백트래킹을 이용한다.
중복되는 순열을 찾을 수 있으므로 중복을 허용하지 않는 set을 이용하여 푼다.
이 때 set을 잘 활용하기 위하여 output을 담을 때 vector를 이용하였고, 찾은 순열들을 저장하기 위해 set<vector>를 사용하였다.
set은 중복을 허용하지 않는 균형이진트리이므로 중복에 대한 걱정은 하지 않아도 된다.
하지만 main함수에서 set<vector>를 출력할 때 iterator를 두개 사용해야 한다.
set 내부의 vector 원소들을 도는 두 번째 iterator는 const_interator로 만들어야 한다는게 중요하다.
이진트리인 set의 특성상 원소들이 자동으로 const가 되므로 set 내부의 vector는 const vector이기 때문이다.

내 맞은 풀이 2

#include<algorithm>
#include<cstdio>
using namespace std;

int n, m, num[8], result[8], check[8];

void ans(int cnt, int start)
{
	if (cnt == m)
	{
		for (int i = 0; i<m; i++)
			printf("%d ", result[i]);
		puts("");
		return;
	}
	int prev_num = -1; 
  // 여기서 prev_num이 함수를 호출할 때마다 생성되는게 포인트임. 
  // 단계별로 모두 다른 prev_num이 호출되므로 그게 중복된 순열을 막아주고, 
  // 서로 다른 칸의 중복된 숫자는 허용한다. 
  // 만약 이걸 전역변수로 두면 그냥 순열의 모든 각 칸에서 중복된 숫자가 사라진다.
	for (int i = start; i < n; i++)
	{
		if (!check[i] && prev_num != num[i])
		{
			check[i] = 1;
			result[cnt] = num[i];
			prev_num = num[i];
			ans(cnt + 1, i);
			check[i] = 0;
		}
	}
}

set 사용하지 않고 이전에 사용된 숫자가 무엇인지 체크함으로써 백트래킹 구현.
함수 내부에서 prev_num을 선언하는게 포인트이다.