가장 큰 수

문제설명

 

 

#include <string>
#include <vector>
#include <algorithm> 
#include <utility>
#include <iostream>

using namespace std;

bool cmp(string A, string B)
{
    return A+B > B+A;
}

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

 

 

=> 각 원소를 더하여 크기를 비교할 경우 시간 복잡도에서 해당 문제를 해결할 수 없습니다. 

=> string형으로 변환 후, 해당 배열을 큰 순으로 정렬하는 과정이 필요합니다.

=> cmp 함수를 생성해 해당 배열을 sorting합니다. 

*** string형태의 숫자이지만  '1'뒤에 '2'가,  '2'뒤에 '3'이 있으므로 cmp함수로 비교를 하여도 숫자형의 비교와 다르지 않습니다. 

 

=> 정렬된 배열은 이미 각 원소중 가장 큰 부분의 수로 정렬되어 있는 상태입니다. 

=> answer에 배열의 원소를 처음부터 끝까지 더하면 됩니다. 

 

** 맨처음 vector의 값이 [0,0,0,0] 일 경우 "0000"이 나오는 경우가 생기므로 예외처리를 해주어야 합니다. 

 

 

 

bool cmp(string A, string B)
{
    return A+B > B+A;
}

*cmp함수