boj,백준) 1039. 교환(C / C++)

1. 문제 링크

www.acmicpc.net/problem/1039

1039번: 교환

 

2. 문제 개요

 

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1≤ i < j ≤ M 인 i와 j를 고른다. 그다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

 

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

 

 

3. 문제 힌트

그리디로 접근하려고 했으나..... 안 될 것 같다.

 

문제 유형을 보니 BFS다.

결국은 전수조사..

그런데 그냥 전수조사를 하면 시간 복잡도는 N은 7자리, 7개 중에 2개를 뽑아서 바꾸니 7C2이고 1번에 21가지이다.

k는 10번이니 21^10이 되므로... 그냥 전수조사는 안 되겠다.

 

알고리즘은 전수조사인데, 어떻게 하면 시간 복잡도를 줄일 수 있을까?

이 문제 유형이 BFS인 이유는 한 번 갔는데 또 두 번 해당 숫자를 보는 것은 또 볼 필요가 없기 때문에.. 어딘가에 담아서 이 숫자가 이전에 확인했던 적이 있는지 구분하는 그런 것이 필요하다.

 

 

4. 문제 풀이

(3) 번에서 말했던 것처럼 전수조사이다 결국.

 

그래서 기존 숫자를 받고, (여기서는 string으로 다룰예정입니다.)

queue에 넣는다.

만약에 시작이 1234라면

queue에서 1개를 꺼내고(1234)

1번째 2번째 바꾼거 queue에 push,

1번째 3번째 바꾼거 queue에 push

1번째 4번째 바꾼거 queue에 push

2번째 3번째,

2번째 4번째,

3번째 4번째,

이렇게 모두 queue에 넣을 것이다.

 

예를 들어서 1번째 2번째를 바꿔서 2134가 되었다고 하자, 그런데 또 1번째 2번째를 바꿔서 1234가 되었을 수도 있다. 

또 어떤 숫자를 잘 바꿔서 1234가 되었다고 하자(가정), 그럼 queue에 1234가 2개 들어가는 것이다. 이렇게 된다면 시간 초과가 날 것이다. 불필요한 연산이기 때문에 제거해줄 필요가 있다.

(다음 연산 때 queue에서 2개를 꺼낼 텐데, 똑같은 반복을 하기 때문에)

 

그래서 여기서는 숫자를 string으로 사용했기 때문에 set을 사용해서 queue에 들어있는 것들을 관리해줄 것이다.

 

그러면,

 

(1) 초기값 queue에 push

(2) K번이니 K번 반복함.

   set선언

   (3) queue size만큼 반복하고, 

         queue에서 pop 하고

         set에 있다면 continue

         없다면 set에 삽입.

         (4) 모든 바꿀 수 있는 순서쌍에 대해 반복

              문자열을 바꾸고 queue에 삽입 후 원상복구

 

이 과정이 끝나면 queue에는 k회 바꾼 숫자들의 후보가 들어있을 것이다.

모두 꺼내 주면서 최댓값으로 추출하고, 

최댓값의 맨 앞자리가 0이면 -1,

그렇지 않으면 해당 값을 출력해주자.

 

여기서 중요한 예외 케이스는

순서쌍을 만드는 도중에도 맨 앞자리의 값이 0이 되면 안 된다.

K회 바꾼 것의 앞자리만 0이 안 되는게 아니고 K회 이전에도 앞자리는0이되면 안되는 점이다.

 

5. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
using namespace std;
 
int k;
queue<string> q;
 
 
void myswap(string &mystr, int left, int right)
{
	char temp = mystr[left];
	mystr[left] = mystr[right];
	mystr[right] = temp;
	return;
}
int main()
{
	string str;
	cin >> str >> k;
	q.push(str);
 
	for (int i = 0; i < k; ++i) {
		set<string> s;
		int qsize = q.size();
 
		for (int j = 0; j < qsize; ++j)
		{
			string item = q.front(); q.pop();
			if (s.count(item) != 0)	
           		continue;
			s.insert(item);
 
			for (int l = 0; l < item.size() - 1; ++l)
				for (int r = l + 1; r < item.size(); ++r)
					if (!(l == 0 && item[r] == '0')) {
						myswap(item, l, r);
						q.push(item);
						myswap(item, l, r);
					}
		}
	}
	string ans="0";
	while (!q.empty()){
		ans = max(ans, q.front());
		q.pop();
	}
	if (ans[0] == '0')
		cout << "-1";
	else
		cout << ans;
	return 0;
}

 

6. 실행 결과