[Programmers] 정렬 > 가장 큰 수

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

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

정수를 이어 붙여 만들 수 있는 가장 큰 수를 만드는 문제다.

예시

[6, 10, 2]

 가 주어졌을 때, 6210이 만들 수 있는 가장 큰 수이다. 즉, 가장 큰 수를 만드려면 앞자리 수가 가장 큰 수부터 나열하면 된다.

하지만 두번째 예시처럼

[3, 30, 34, 5, 9]

앞자리가 가장 큰 수부터 나열하게되면 3 30 34는 앞자리가 3으로 같으므로 정렬이 되지 않는다.

9 5 34 3 30 으로 정렬하기 위해서는 첫째자리가 같을 경우, 두번째 자리를 보고 비교, 두번째 자리도 같을 경우, 세번째 ...

이런 방법으로 도전했지만 잘 해결되지 않아서 다른 방법으로 접근했다. 

앞자리 수와 뒷자리 수를 합쳐 둘 중 더 큰수를 앞에 나오게 해서 정렬했다.

ex) 3 30의 경우, 330 > 303 이므로 3을 앞에두게 한다.

 

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

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

---

테스트케이스

[3,30,34,5,9] 9534330

[6,10,2] 6210

[0,0,0] 0