<Programmers> Sort_가장 큰 수 c++

numbers의 길이가 최대 100,000까지 가능하므로 순서를 재배치하여 만들 수 있는 가지수는 최대 100000!이 된다. 따라서 모든 경우의 수를 구하는 것은 잘못된 접근 방법이다.

문제의 예시 처럼 {6, 10, 2} 가 있을 때 "610"과 "106", "62"과 "26", "102"과 "210"을 비교했을 때 6은 10과 2보다 앞, 10은 2보다 뒤에 오는 것이 제일 큰 수로 나타내진다.

즉 숫자가 string으로 주어졌을 때 {a,b,c} 을 정렬하려고 할 때
a+b와 b+a 중 큰 수, b+c와 c+b중 큰 수, a+c와 c+a중 큰 수가 앞으로 오게 정렬을 하면 된다.

1. 주어진 numbers를 문자열로 변환

    vector<string> tmp;
    for (int i=0; i<numbers.size(); i++) 
        tmp.push_back(to_string(numbers[i]));

2. compare 함수 정의
   (compare 함수 정의 하는 부분은 할 때마다 너무 헷갈린다..)

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

전체 코드

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

using namespace std;

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

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

*처음에 if (answer[0]=='0') return "0"; 를 뻬먹었더니 몇 문제에서 통과가 안 됐다.