1. 문제 분석하기

1.1. 문제 의도

• 시뮬레이션 문제입니다.

2. 문제 해결하기

• 이 문제는 간단하지만, 숨겨진 예외조건을 찾기 까다롭습니다.
  연산을 K번 할 수 없는 경우 -1을 출력한다는 말을 이해하기 어렵기 때문입니다.
  1. N = 1,000,000인 경우, 연산을 수행할 수 없습니다.
  2. N = 1~9 또는 N = 10, 20, 30, …, 90인 경우, 연산을 수행할 수 없습니다.
• 왜냐하면, 연산을 1회 수행할 때 무조건 맨 앞이 0이 돼서 진행할 수 없기 때문입니다.
• 연산을 수행하다보면 중복되는 수가 등장합니다.
  • .
  • 중복되는 수는 기하급수적으로 증가해서 메모리 초과를 유발합니다.
    반드시 중복을 제거해줘야 합니다.
  • 수의 범위가 커서 bool 타입 배열로는 판단이 힘듭니다. 따라서 unordered_set 자료구조를 이용해서 중복을 자동으로 제거하도록 합니다.

1. queue자료구조를 이용해서 이번 loop에 queue안에 들어있는 요소들의 교환조합을 구합니다.
2. 모든 교환조합은 set에 집어넣고 중복을 제거합니다.
3. 다음 loop로 가기 전에 set에 남아있는 요소들을 queue에 다시 넣습니다.

• 이때 연산을 K번 수행하기 전에 queue가 비어버리면 K번 진행할 수 없게되므로 -1을 출력합니다.

3. 코드

#include <iostream>
#include <string>
#include <queue>
#include <unordered_set>
using namespace std;

int main() {
    	ios::sync_with_stdio(false), cin.tie(NULL);
	int K, answer = 0;
	string N;
	cin >> N >> K;
	
	// 예외처리 :: 한자리, 끝이 0인 두자리, 백만
    	if (N == "1000000") { cout << N; return 0; }
    	if (N.size() == 1) { cout << -1; return 0; }
    	if (N.size() == 2 && N[1] == '0') { cout << -1; return 0; }
	
	queue<string> q;
	q.push(N);
	
	while(!q.empty() && K--) {
		unordered_set<string> s;
		
		int cnt = q.size();
		while(cnt--) {
			string num = q.front();
			q.pop();
			// 모든 조합을 구하고, set에 삽입해서 중복 제거.
			for (int i = 0; i < num.size() - 1; ++i)
				for (int j = i + 1; j < num.size(); ++j) {
                    			if (i == 0 && num[j] == '0') continue;
					swap(num[i], num[j]);
					if (s.find(num) == s.end()) {
						if (K == 0) answer = max(answer, stoi(num));
						q.push(num);
						s.insert(num);
					}
					swap(num[i], num[j]);
				}
		}
	}
    	// 여기서 queue에서 answer를 구하려고 하면 메모리 초과.
	if (K >= 0) cout << -1;
	else cout << answer;
}

4. 결과