가장 큰 수 / 정렬

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

처음에 이 문제를 보고, 모든 경우의 수를 조합해야된다는 생각에 바로 브루트 포스로 문제를 해결하였다.
코드 작성을 끝마치고 나서야 제한 사항이 눈에 들어왔고 10만이라는 숫자를 뒤늦게 확인하였다..
당연히 시간 초과가 날 것이라고 판단하고 다시 문제를 어떻게 해결해야될지 고민이 되었다.

입출력의 예를 살펴보니 앞자리의 숫자가 큰 숫자가 우선 순위가 높다는 것을 알게 되고, 각 숫자의 첫번째 자리 숫자를 비교해야되나 하는 생각이 들던 찰나에 3, 30, 34 와 같이 앞자리의 숫자가 같을 경우엔 비교를 할 수 없음을 깨달았다.

아에 priority queue에서 비교 함수를 작성해 a + b 조합과 b + a 조합을 직접 비교하는 것으로 결정하고 재 구현하였다.

✅ priority queue 사용 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

string solution(vector<int> numbers)
{
    auto cmp = [](const string& a, const string& b)
        {
            return a + b < b + a;
        };

    priority_queue<string, vector<string>, decltype(cmp)> pq(cmp);

    for (int number : numbers)
    {
        pq.push(to_string(number));
    }

    string result;
    while (!pq.empty())
    {
        result += pq.top(); pq.pop();
    }

    if (result[0] == '0') result = "0";

    return result;
}

priority queue 우선순위를 사용해서 문제는 해결하였지만 과연 이게 최선인지 고민해본 결과,
pq는 각 요소에 대해 push되는 상황에 정렬을 유지해야되기 때문에 비용이 지속적으로 발생할 것 같다는 생각이 들었다.
주어진 numbers 배열을 string으로 변환해서 저장한 후에 한 번에 sort를 사용해 정렬하는게 어떨까 싶었다.

 

✅ sort algorithm 사용 코드

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

using namespace std;

string solution(vector<int> numbers)
{
    vector<string> str_numbers;

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

    sort(str_numbers.begin(), str_numbers.end(), [](string a, string b)
        {
            return a + b > b + a;
        });

    string result;
    for (string number : str_numbers)
    {
        result += number;
    }

    return result;
}

sort로 딱 한 번 정렬할 수 있어 불필요한 오버헤드를 줄였고, 코드 또한 더 간결하게 표현되었다.