백준 15666 N과 M (12) C++

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

15666번: N과 M (12)

 

복기

아래와 같은 N과 M 시리즈 문제

https://smallpants.tistory.com/220

 

이번엔 입력되는 수에 중복이 있다.

예를들어 { 9, 7, 9, 1 }처럼 들어오는데 정렬해서 사용하므로 { 1, 7, 9, 9 }로 생각하고 시작

근데 문제는 1로 시작해서 2개 뽑는다면 11 17 19 19 처럼되는데 19가 두번 나오면 안된다.

 

이전에 비슷한 문제를 풀땐 그냥 중복 제거를 위해 set에다가 값 다 때려넣어버리고 마지막에 set에 있는 수열들을 다 출력해버렸었다.

아래의 정답코드 2번이 해당 방식인데 이렇게 하면 저장공간을 많이 써야하고 같은 수열을 여러번 만드니까 시간도 더 써야한다.

 

구글링해본 결과 좋은 아이디어는 현재 temp에 M - 1개가 들어있을때 

값을 넣으면서 해당 값을 prev 변수에 저장한다.

그리고 나서 M개가 됐으니 해당 수열은 출력

다음 재귀에 다시 M - 1개가 있는데 이때 넣으려는 값이 prev와 같다면 똑같은 수열을 만드는거니까 그냥 넘긴다.

 

즉 매번 있던 수열인지 체크할 필요도 없이 M - 1개 채워진 상황 -> M개 채워지는 상황에서 최근 수열의 마지막값과 현재 마지막으로 넣으려는 값이 같은지만 체크하면 된다.

 

정답코드

1) prev를 사용하는 경우

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

vector<int> vec, temp;
int N, M;
void recursion(int count, int start)
{	
	if (count == M) {		
		for (auto t : temp) { cout << t << ' '; }
		cout << '\n';
		return;
	}

	int prev = -1;
	for (int i = start; i < N; i++) {
		if (prev != vec[i]) {
			prev = vec[i];
			temp[count] = vec[i];
			recursion(count + 1, i);			
		}
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL);

	cin >> N >> M;
	vec.resize(N);
	temp.resize(M);

	for (int i = 0; i < N; i++) { cin >> vec[i]; }
	sort(vec.begin(), vec.end());

	recursion(0, 0);

	return 0;
}

 

2) set을 사용하는 경우

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

vector<int> vec, temp;
set<vector<int>> s;
int N, M;
void recursion(int count, int start)
{	
	if (count == M) {		
		s.insert(temp);
		return;
	}

	for (int i = start; i < N; i++) {
		temp[count] = vec[i];
		recursion(count + 1, i);		
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL);

	cin >> N >> M;
	vec.resize(N);
	temp.resize(M);

	for (int i = 0; i < N; i++) { cin >> vec[i]; }
	sort(vec.begin(), vec.end());

	recursion(0, 0);
	for (auto& per : s) {
		for (int i : per) {
			cout << i << ' ';
		}
		cout << '\n';
	}

	return 0;
}