백준 1039 - 교환

 

 

문제 설명

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N의 각 자릿수를 K번 교환하여 만들 수 있는 최댓값을 구하는 문제이다.

 

처음에는 N의 각 자릿수를 정렬하여 최대한 비슷하게 만드는 방식으로 문제를 풀려했었다.

k번의 교환을 통해 0번째부터 k번째 수를 확정해가면 된다 생각했다.

하지만, 이 방법은 반만 정답이다.

만약 k가 N의 자릿수보다 많다면 곤란해진다.

따라서, 해당 방법이 아닌 다른 방법이 필요하다.

 

k-1번째 교환에서 큰 수를 만들었다 하여도 k번째에 더 작아질 수 있다.

반대로 k-1번째에서는 작은 수였지만 k번째에 더 큰 수로 만들 수도 있다.

즉, 교환이 일어난 모든 상황을 살펴보며 최댓값을 구해야 한다.

즉, BFS를 사용해야 한다.

 

BFS를 진행하는 것은 간단하다.

0번 자리부터 하나씩 바꿔보며 확인하면 된다.

만약 k번째 교환이 일어났을 경우 최댓값을 갱신한다.

시간과 메모리를 줄이기 위해 k번째 교환하여 같은 수가 나온다면 해당 분기는 더 이상 진행하지 않게 하였다.

while (!q.empty() && tryNum++ <= K)
{
    set<string> checked;
    int size = q.size();
    for (int t = 0; t < size; t++)
    {
        string current = q.front();
        q.pop();

        for (int i = 0; i < M-1; i++)
        {
            for (int j = i + 1; j < M; j++)
            {
                if (i == 0 && current[j] == '0') continue;
                string copied = current;
                swap(copied[i], copied[j]);

                if (checked.find(copied) != checked.end()) continue;

                if (tryNum == K)
                {
                    ans = max(ans, Convert(copied));
                    continue;
                }

                q.push(copied);
                checked.insert(copied);
            }
        }
    }
}

문자열을 복사한 이유는 원본으로 다시 바꾸는 작업을 하지 않기 위해서이다.

복사하는 비용이 있지만, 코드의 가독성을 우선시 하였다.

해당 BFS는 라운드별로 진행되어야 하기 때문에 for문으로 한 겹 쌓여있다.

따라서 들여 쓰기가 다른 것보다 많이 된다.

이러한 상황에서 또다시 조건문으로 들여 쓰기를 하지 않기 위해 앞에서 분기를 종료하도록 하였다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

string N;
int K, M;

int Convert(string s)
{
    int num = 0;
    for (int i = 0; i < s.size(); i++)
    {
        num *= 10;
        num += s[i] - '0';
    }

    return num;
}

int BFS()
{
    queue<string> q;
    q.push(N);
    int tryNum = 0;
    int ans = -1;

    while (!q.empty() && tryNum++ <= K)
    {
        set<string> checked;
        int size = q.size();
        for (int t = 0; t < size; t++)
        {
            string current = q.front();
            q.pop();

            for (int i = 0; i < M-1; i++)
            {
                for (int j = i + 1; j < M; j++)
                {
                    if (i == 0 && current[j] == '0') continue;
                    string copied = current;
                    swap(copied[i], copied[j]);

                    if (checked.find(copied) != checked.end()) continue;

                    if (tryNum == K)
                    {
                        ans = max(ans, Convert(copied));
                        continue;
                    }

                    q.push(copied);
                    checked.insert(copied);
                }
            }
        }
    }

    if (tryNum != K) return -1;
    else return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;
    M = N.size();

    cout << BFS();
 
    return 0;
}

---