Leetcode - 179. Largest Number

문제

배열로 주어지는 값을 합쳤을때 가장 큰 수가 나오도록 조합하라.

Input: nums = [10,2]
Output: "210"

Input: nums = [3,30,34,5,9]
Output: "9534330"

해결

32 3 이 있을때 32|3 보다 3|32 더 크다. 따라서 sort의 compare함수를 이 두 경우를 비교하도록 하면 된다. (discussion 참고). 추가로 std::sort()의 custom compare함수 사용법을 기억할것.

cmp(int a, int b) {
	//오름차순(a < b) 가 유지되어야한다면 true리턴
    //반대는 false리턴
}

class Solution {
public:
    static bool custom_cmp(int a, int b) {
        string sa = std::to_string(a);
        string sb = std::to_string(b);
        if (sa + sb > sb + sa)
            return true; // 순서 a b 유지
        else
            return false;
    }
    string largestNumber(vector<int>& nums) {
        std::string ret;
        std::sort(nums.begin(), nums.end(), custom_cmp);
        for (auto it: nums)
            ret = ret + std::to_string(it);
        if (ret[0] == '0')
            return "0";
        return ret;
    }
};