1. 문제 분석하기
1.1. 문제 의도
2. 문제 해결하기
- 이 문제는 간단하지만, 숨겨진 예외조건을 찾기 까다롭습니다.
연산을 K번 할 수 없는 경우 -1을 출력한다는 말을 이해하기 어렵기 때문입니다.
N = 1,000,000
인 경우, 연산을 수행할 수 없습니다.
N = 1~9
또는 N = 10, 20, 30, …, 90
인 경우, 연산을 수행할 수 없습니다.
- 왜냐하면, 연산을 1회 수행할 때 무조건 맨 앞이
0
이 돼서 진행할 수 없기 때문입니다.
- 연산을 수행하다보면 중복되는 수가 등장합니다.
- .
- 중복되는 수는 기하급수적으로 증가해서 메모리 초과를 유발합니다.
반드시 중복을 제거해줘야 합니다.
- 수의 범위가 커서 bool 타입 배열로는 판단이 힘듭니다. 따라서
unordered_set
자료구조를 이용해서 중복을 자동으로 제거하도록 합니다.
queue
자료구조를 이용해서 이번 loop에 queue안에 들어있는 요소들의 교환조합을 구합니다.
- 모든 교환조합은
set
에 집어넣고 중복을 제거합니다.
- 다음 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;
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();
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]);
}
}
}
if (K >= 0) cout << -1;
else cout << answer;
}
4. 결과