가장 큰 수(Level2)

• 문제 링크: 코딩테스트 연습 > 정렬 > 가장 큰 수

• 문제 이해

  1. 배열 안의 수들을 조합하여 가장 큰 수를 만듭니다.
  2. 만약, [3, 30, 34, 5, 9]라는 배열이 있다면, 9534330이 가장 큰 수입니다.

• 알고리즘 구현

  1. 기본적으로, 자릿수를 통째로 가져다 붙이는 위와 같은 문제들은 string으로 풀이하는 편이
     훨씬 빠르다고 생각했습니다. 또한, string에서 비교연산은 앞자리 수부터 비교하기 때문에
     int 자료형에서의 비교 방식과 같습니다.
  2. 따라서 우선적으로, 주어진 vector<int> 자료형을 vector<string>으로 변경합니다.
  3. 이 문제의 가장 헤맸던 부분은, 기본적인 정렬(오름차순 혹은 내림차순)으로만 문제를 풀려고
     했던 것입니다. 하지만, <algorithm>의 sort를 costomizing하면 해결하기 편리합니다.
  4. 한 예로, [6, 10, 2]라는 배열이 주어진다면, 6과 10을 비교했을 때, 610이 106보다 큽니다.
     따라서, 6다음 10을 정렬하는 것이 유리합니다. 또한, [10, 2]라면, [2, 10]이 유리하고,
     [6, 2]라면, [6, 2]가 유리합니다. 따라서, 위 배열은 [6, 2, 10]으로 나타낼 수 있습니다.
  5. 이렇게, 정렬 알고리즘 안에서 비교 방식을 costomizing 하는 것이 핵심임을 알 수 있습니다.
  6. 위와 같이 정렬이 마무리 된다면, 각 요소를 그냥 잇달아 붙이기만 하면 됩니다.
  7. 예외케이스: [0, 0, 0]과 같은 배열을 받더라도, 결과는 0이어야하기 때문에, 정렬의 가장 첫
     값이 0이라면, 0을 반환합니다.

• 알고리즘

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

using namespace std;

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

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