15663. n과 m 9번_중복 순열 제거.

욥·2025년 6월 1일

백준 알고리즘

목록 보기

173/270

정말 중요한 중복 순열 제거

이해를 먼저 해야 한다.

250827 업데이트

5 3 (cin >>n , cin >> m)(5개 중에서 3개를 뽑아서 중복되지 않게 나타내라. )
1 3 7 7 7

: 1 3 7 / 1 7 7 / 3 7 7 / 7 7 7

어떻게 구현할까?
: 기존의 조합 코드로는 불가하다.
코드를 보자.
: 내부에서 for문 돌릴때 m값으로 순회하고 있다.

어떻게 진행되는지를 자세히 보자.

왜 그런지 살펴보자.
: 1 3 7 7 7
일단 카운티 배열은 반드시 필요하다.
for(int i =0; i < m; ++i) 를 반복문이라고 표기하겠다.
cntV 를 카운팅 이라고 하겠다.

반복문에 의해서 i = 0 진행하므로, 카운팅[1] 은 0이 아니므로 resV에 1이 삽입되고,
카운팅[1]-- 되어서 카운팅[1] = 0이 된다.
재귀 진행 반복분에 의해서 i =0 을 진행하려고 하는데,
v[0] = 1이고, 카운팅[1] = 0 이기 때문에
i = 1; 을 진행한다. v[1] = 3이고, 카운팅[3] = 1; 이므로 삽입 가능 resV에 3 삽입된다. 카운팅[3] = 0 이된다.
재귀 진행 반복문 도는데, 카운팅 조건에 의해서 i = 2; 진행한다. res.push(v[2]) 삽입되므로, res = {1,3,7} 이 되고,
카운팅[7] = 2; 가 된다.
res 3개를 출력하고 return; 함.
반복문으로 돌아와서 for문 현재 i = 3; 이다.
반복분의 범위는 m까지이므로, 해당 재귀는 끝난다.
그리고 res에 마지막에 넣은거 pop하고, 카운팅 증가.
res = {1,3} . cnt[7]=> 3; 으로 복귀
반복문에서 i = 2; 일 때 재귀한 곳으로 복귀한다.
pop 을 진행하고, 카운팅 증가.
res = {1}, cnt[3] =>1; 이 된다.
for문 맨처음으로 돌아온다. 현재 i = 1; 까지의 과정을 마쳤다. i = 2;를 진행한다. ...
res = {1, 7} 집어넣고, 첫번째 for문은 마지막 idx이고,
다시 재귀 진입. for 진행하는데, cnt[3] = 1; 이기 때문에 이거 또 넣는다. res = {1, 7 , 3} 이 된다. 출력
위의 상황은 for에서 i = 1인 경우이고, i = 2인 경우 진행해야지 res = {1, 7 , 7 이 되고, 출력
i = 2; 이므로, 복귀 해서 pop 을 진행한다....

아래는 250827 전에 set으로 한 내용이다.
웬만하면 set으로 하지 말자. 메모리 엄청 커진다.
=> 2MByte 나 차이가 난다.

반례

https://www.acmicpc.net/board/view/149855

생각해야 할 부분
: 반례에 대해서 5분만 투자해보자.

풀이전략

: 중복되는 값들을 set 으로 처리하려고 했다.

그래서 set ss; 으로 해서 진행했는데,
46퍼센트에서 틀림...

반례가 있다.

void backTracking(int idx)
{

	if (resV.size() == m)
	{
		string s;

		for (const auto& iter : resV)
		{
			s += to_string(iter);
		}

		if (ss.find(s) == ss.end())
		{
			for (const auto& iter : resV)
			{
				cout << iter << " ";
			}
			ss.insert(s);
		}
		// 이미 존재한다면 return
		else
		{
			return;
		}

		cout << '\n';

		// 중복된 값 출력에 대한 처리를 해야 한다. 
		// 해시로 하는게 좋을 듯하다. 

		return;
	}


	// 동일한 위치 중복 넣을 수 없다! 
	// 불체크 하자. 

	for (int i = 0; i < n; ++i)
	{
		if (check[i] == true)
			continue;

		check[i] = true;
		resV.push_back(v[i]);
		backTracking(i);

		resV.pop_back();
		check[i] = false;

	}


}

이 코드에서
입력값 : 아래 처럼 하면 어떻게 될까??????????
3 2
1 12 21