[C++][백준 1039] 교환

문제설명은 더보기를 눌러주세요

문제

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

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

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

입력

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

 

-풀이-

1. 큐를 이용한 BFS와 swap(i, j) 함수를 이용하여 쉽게풀 수 있습니다.

2. swap(i, j) 함수를 사용할 경우, string의 i번째 index와 j번째 index를 바꿔줍니다.

3. 초기string 부터 시작하여, swap함수를 이용하여 1번 swap된 string을 모두 큐에 넣어줍니다.
    1번 swap된 string을 큐에서 꺼내고, 한번 더 swap하여 2번 swap된 string을 모두 큐에 넣어줍니다.
    2번 swap된 string을 큐에서 꺼내고, 한번 더 swap하여 3번 swap된 string을 모두 큐에 넣어줍니다.
    ....(너비우선탐색)

4. 진행중 0이 맨 앞으로 온 경우 혹은 이미 나왔던 string은 큐에 넣어주지 않고 무시

5. K번 연산한 경우들 중 stoi(string to integer) 함수를 이용하여 최댓값을 구합니다. 
    

 

-코드-

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<cstring>
using namespace std;
queue<pair<string, int> > q;
int visit[1000001][11];
int main(){
    memset(visit, 0, sizeof(visit));
    string str;
    int K, ans=0;
    cin >> str >> K;
    
    q.push(make_pair(str, 0));
    while(!q.empty()){
        pair<string, int> cur = q.front(); q.pop();
        if(cur.second == K) { // K번 연산했을 경우
            ans = max(ans, stoi(cur.first));
            continue;
        }
        string curStr = cur.first;
        for(int i=0; i<curStr.size()-1; i++){
            for(int j=i+1; j<curStr.size(); j++){
                swap(curStr[i], curStr[j]);
                if(curStr[0] == '0' || visit[stoi(curStr)][cur.second+1]) { // 맨앞이 0 이거나 이미 나온적이 있으면
                    swap(curStr[i], curStr[j]); // 다시 되돌려줌 
                    continue;
                }
                q.push(make_pair(curStr, cur.second+1)); //swap한 string, 연산횟수+1
                visit[stoi(curStr)][cur.second+1] = 1;
                swap(curStr[i], curStr[j]); // 다시 되돌려줌
            }
        }
    }
    if(ans == 0) cout << "-1";
    else cout << ans;
}