[Programmers/C++] 가장 큰 수

시간 복잡도

• n번 순회 + 정렬을 사용하므로 $O(n+nlogn)$의 시간 복잡도가 발생합니다.
• n은 최대 100,000이기 때문에 시간 복잡도는 충분합니다.

문제 접근법

• 문자열로 바꾼 후 더해진 문자열 값이 크도록 내림차순하여 정렬합니다.
• 예를 들어 3, 30이 있다면 330이 303보다 큰데 이 때 "330", "303"을 비교하여 정렬하면 3, 30 순으로 정렬됩니다.

코드

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

using namespace std;

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

string solution(vector<int> numbers) {
    string answer = "";
    
    vector<string> temp;
    
    for(int num : numbers)
        temp.push_back(to_string(num));
    
    sort(temp.begin(), temp.end(), compare);
    
    for(string num : temp)
        answer+=num;
    
    if(answer[0]=='0')
        return "0";
    
    return answer;
}