[백준] 15644 N과M(10) c++

정답률 80이길래 쉬울 줄 알았는데 3번이나 틀려서 현타왔다,,

"중복되는 수열을 여러 번 출력하면 안되며, " 라는 조건이 어려웠다.

바로 이전에 출력한 수열하고만 비교하면 되는 줄 알았는데

이전에 출력한 수열을 전부다 비교했어야했다.

입력을 string 으로 받으면 sort 할때 제대로 정렬이 안된다. 2,10 하고 비교하면 10이 먼저 오게 된다.또한 수열을 string 으로 바꾸어서 이전에 만들었던 수열을 비교해줄려고 했었는데 잘 안되었다.결국 벡터배열에 수열을 저장해서 전부 비교해주었다.

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

int num[9];
int N, M;
int arr[8];
bool visit[8];
bool chk = false;
int cnt = 0;
vector<int> v[45000];

void backtracking(int depth, int index)
{
	if (depth == M)
	{
		
		for (int i = 0; i < cnt; i++)
		{
			for (int j = 0; j < M; j++)
			{
				
				if (v[i][j] != arr[j])
					break;
				if (j == M - 1)
				{
					return;
				}
			}
		
		}
	

		for (int i = 0; i < M; i++)
		{
			v[cnt].push_back(arr[i]);
			cout << arr[i] << " ";
		}
		cnt++;
		
		cout << endl;
		
		return;
	}

	for (int i = index; i < N; i++)
	{
		if (!visit[i])
		{
			visit[i] = true;
			arr[depth] = num[i];
			backtracking(depth + 1, i + 1);
			visit[i] = false;
			
				
		}
	}
}

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> num[i];
	sort(num, num + N);

	backtracking(0, 0);
}

 

 

다른 분들의 코드를 보고 나니까 내 코드가 너무 복잡한 것 같다.

중복이 안된다는 조건을 다음과 같이 구현하셨다.

*robert334님코드

for (i = y; i < n; i++) {
		B[x] = i;
		if (A[i - 1] != A[i] || i == y)//이전에 넣었던 숫자이면 안된다. 단 i==y일 경우 새로운 depth에 넣는 것이므로 괜찮다.
			S(x + 1, i + 1);
		B[x] = 0;
	}

*qudgh0745님코드

int prev_num = 0;//새로운 depth일때 초기화
	for (int i = idx; i < n; i++) {
		if (arr[i] != prev_num) {//이전에 넣었던 숫자면 x
			arr1[cnt] = arr[i];
			prev_num = arr[i];
			dfs(cnt + 1, i + 1);
		}
	}

 

 

-고친 코드

#include<iostream>
#include<algorithm>


using namespace std;

int num[9];
int N, M;
int arr[8];
bool visit[8];
bool chk = false;
int cnt = 0;


void backtracking(int depth, int index)
{
	if (depth == M)
	{
		
		

		for (int i = 0; i < M; i++)
		{
		
			cout << arr[i] << " ";
		}
		
		cout << endl;
		
		return;
	}

	for (int i = index; i < N; i++)
	{
		
		if (num[i] == num[i - 1] && i != index)continue;
			arr[depth] = num[i];
			backtracking(depth + 1, i + 1);
			
		
	}
}

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> num[i];
	sort(num, num + N);

	backtracking(0, 0);
}