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

💻 C++ 기반

코딩테스트 연습 - 가장 큰 수
https://school.programmers.co.kr/learn/courses/30/lessons/42746

✔️ 정렬을 해야 하는 배열의 길이가 최대 100,000이므로 시간 복잡도가 O(N^2)인 정렬을 쓰면 안된다.
✔️ C++ 라이브러리 중에 <algorithm>의 sort 함수를 사용하면 시간 복잡도가 O(NlogN)이다.
✔️ 입력으로 주어지는 배열에는 같은 숫자가 중복해서 들어갈 수 있다.
✔️ 입력으로 주어지는 배열에 다 0만 있다면 답은 0이 되어야 한다. (0000… 아님!)

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

using namespace std;

bool compare(int num1, int num2)
{
    string str1 = to_string(num1);
    string str2 = to_string(num2);
    
    string temp1 = "";
    temp1 += str1;
    temp1 += str2;
    
    string temp2 = "";
    temp2 += str2;
    temp2 += str1;
    
    int len = str1.length() + str2.length();
    
    for (int i = 0; i < len; i++)
    {
        if (temp1[i] > temp2[i])
        {
            return true;
        }
        else if (temp1[i] < temp2[i])
        {
            return false;
        }
    }
    
    return false;
}

string solution(vector<int> numbers) {
    string answer = "";
    
    sort(numbers.begin(), numbers.end(), compare);
    
    for (int i = 0; i < numbers.size(); i++)
    {
        if (answer == "0" && numbers[i] == 0)
        {
            answer = "0";
        }
        else
        {
           answer += to_string(numbers[i]); 
        }
    }
    
    return answer;
}