1244. [S/W 문제해결 응용] 2일차 - 최대 상금

문제

SW Expert Academy

다음과 같이 입력이 주어질 경우 {123 1} 123을 1번 자리를 교환해 가장 큰 수를 만들어야 한다.

예시에서는 1과 3을 바꿔 321이 정답이다.

{94 2} 일 경우 94 -> 49 -> 94 이다.

처음에는 단순히 백트래킹 기법으로 모든 자리를 교환해 그 중 가장 큰 수를 출력할려 했다.

sol(st, change); //입력 받은 String 숫자배열, change는 교환할 수 있는 수

void sol(string s, int cnt)
{
    if (cnt == 0) //cnt가 0이면 다 교환했다는 의미 이므로 최댓값을 갱신
    {
        int temp = stoi(s);
        ans = max(ans, temp);
        return;
    }

    for (int i = 0; i < s.length() - 1; i++) //백트래킹 부분
    {
        for (int j = i + 1; j < s.length(); j++)
        {
            swap(s[i], s[j]);
            sol(s, cnt - 1);
            swap(s[i], s[j]);
        }
    }
}

위의 경우에는 시간초과가 나오게 된다....

따라서 중복되는 수는 체크를 해줘야한다.

예를 들어 {333 1} 로 주어지면 333, 333, 333이 세번 나오게 되는데 중복체크를 안해주면 시간이 걸린다.

chk[a][b]가 true이며는 b번 교환했을 때, a라는 값은 이미 나온 값이다.

void sol(string s, int cnt)
{
    if (cnt == 0)
    {
        int temp = stoi(s);
        ans = max(ans, temp);
        return;
    }

    for (int i = 0; i < s.length() - 1; i++)
    {
        for (int j = i + 1; j < s.length(); j++)
        {
            swap(s[i], s[j]);
            int Temp = stoi(s);
            if (chk[Temp][cnt-1] == false)
            {
                chk[Temp][cnt-1] = true;
                sol(s, cnt - 1);
            }
            swap(s[i], s[j]);
        }
    }
}

---

전체 코드이다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <cstring>
using namespace std;
int ans;
bool chk[1000000][11];
int num = 1;
void sol(string s, int cnt);
int change;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        string st;
        cin >> st;

        cin >> change;

        sol(st, change);

        cout << '#' << num << ' ' << ans << '\n';
        ans = 0;
        memset(chk, false, sizeof(chk));
        num++;
    }
    return 0;
}
void sol(string s, int cnt)
{
    if (cnt == 0)
    {
        int temp = stoi(s);
        ans = max(ans, temp);
        return;
    }

    for (int i = 0; i < s.length() - 1; i++)
    {
        for (int j = i + 1; j < s.length(); j++)
        {
            swap(s[i], s[j]);
            int Temp = stoi(s);
            if (chk[Temp][cnt-1] == false)
            {
                chk[Temp][cnt-1] = true;
                sol(s, cnt - 1);
            }
            swap(s[i], s[j]);
        }
    }
}

더 좋은 풀이법도 있다 (시간이 더 빠름)

https://yabmoons.tistory.com/307