[Leetcode/C++] 179_Largest Number

문제는 다음과 같습니다.
저는 우선순위 큐, 그리고 우선순위 큐 안에서 연산자 오버로딩을 통한 정렬을 이용하여 문제를 해결하였습니다.
풀이는 다음과 같습니다.

class Solution {
public:
    struct compare{
        bool operator()(int a, int b){
            string s1 = to_string(a); string s2 = to_string(b);
            return s1+s2 < s2+s1; // string으로 비교
        }
    };
    
    string largestNumber(vector<int>& nums) {
        
        priority_queue<int, vector<int>, compare> pq;
        
        for(int i=0; i<nums.size(); i++){
            pq.push(nums[i]);
        }
        
        string s;
        
        while(!pq.empty()){
            s += to_string(pq.top());
            pq.pop();
        }
        
        if(s[0]=='0') return "0";
        else return s;
    }
};

음 이 문제에서 헷갈렸던 부분은,
처음에 단순히 return s1 < s2; 라고 했었는데, 문제에서 잘 보면
예를들어 3 과 30을 비교할 때, 우선순위가 3이 30보다 높습니다.
저는 처음에 이 경우를 빼 놓고 생각을 했었는데요,
그래서 다시 생각을 해서, 두 문자열을 더했을 때 즉 330과 303을 비교해보았을 때, 왼쪽이 더 큰 것을 알 수 있습니다.

그래서 return s1+s2 < s2+s1; 으로 고쳤습니다!

그리고, 저는 우선순위 큐를 이용하였는데, discussion에서 벡터의 정렬을 이용한 좋은 풀이도 있어서 가져와봤어요 ㅎㅎ

class Solution {
public:
     string largestNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end(),[](int &a,int &b){
            string s1=to_string(a);
            string s2=to_string(b);
            return s1+s2>s2+s1;
        });
        string ans="";
        for(int i=0;i<nums.size();i++){
            string s=to_string(nums[i]);
            ans += s;
        }
        if(ans[0]=='0'){
            return "0";
        }
        return ans;
    }
};