[프로그래머스] 프로그래머스 Level2 가장 큰 수 C++

문제

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

풀이

정렬을 통해서 해결할 수 있었던 문제이다. numbers에 들어온 값들을 문자열 백터에 새로 담아주고 compare 조건을 구현해서 정렬해 주고 각 원소들을 더해주면 된다. compare에 a + b > b + a라는 조건을 구현해 주었는데 예를 들어 34, 33를 compare 할 때 a + b => 3433, b + a => 3334이므로 34를 더 큰 값으로 정렬해줄 수 있었다.

정렬 후에 문자열 백터의 가장 큰 원소가 0이면 0을 리턴해주고 0이 아니라면 모든 원소들을 더해준 것이 정답이다.

문제에 처음 접근할때는 백트래킹으로 접근해서 모든 numbers의 원소에 대해 순열을 구해주어 최댓값을 구해줬는데 시간초과가 났었다. 아무래도 길이랑 원소가 각각 최대 100000, 1000이다보니 터질 수 밖에 없었다. 백준에도 이런 문제가 있다면 아마 백트래킹으로도 풀 수 있을 거 같다?

코드

#include <string>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

bool compare(string a, string b)
{
    return a + b > b + a;
}

string solution(vector<int> numbers) {

    string answer = "";

    vector<string> vStr;

    for (int number : numbers)
    {
        vStr.push_back(to_string(number));
    }

    sort(vStr.begin(), vStr.end(), compare);

    if (vStr[0] == "0")
    {
        return "0";
    }
    else
    {
        for (string element : vStr)
        {
            answer += element;
        }
    }
    
    return answer;
}

시간초과 코드

#include <string>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int arr[1001];
string Large = "";
bool isused[1001];

void func(int k, int size, vector<int> numbers)
{
    if (k == size)
    {
        string dummyStr;

        for (int i = 0; i < size; i++)
        {
            string temp = to_string(arr[i]);
            dummyStr += temp;
        }
        if (dummyStr <= Large)
        {
            return;
        }
        else
        {
            Large = dummyStr;
            return;
        }

    }

    for (int i = 0; i < size; i++)
    {
        if (!isused[numbers[i]])
        {
            isused[numbers[i]] = true;
            arr[k] = numbers[i];
            func(k + 1, size, numbers);
            isused[numbers[i]] = false;
        }
    }
}

string solution(vector<int> numbers) {
    string answer = "";

    memset(isused, false, sizeof(isused));
    memset(arr, false, sizeof(arr));
    int size = numbers.size();

    func(0, size, numbers);

    answer = Large;

    return answer;
}