프로그래머스 - 가장 큰 수 - C++

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

프로그래머스

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(int a, int b)
{
    string sa=to_string(a);
    string sb = to_string(b);
    return sa+sb > sb+sa;
}
string solution(vector<int> numbers) {
    string answer = "";
    stable_sort(numbers.begin(), numbers.end(), compare);

    int maxV=0;
    
    for (int i = 0; i < numbers.size(); i++)
    {
        if(maxV<numbers[i])maxV=numbers[i];
        answer += to_string(numbers[i]);
    }
    if(maxV==0)return "0";
    return answer;
}

주어진 숫자배열에서 각 원소들을 붙여서 만들 수 있는 가장 큰 수를 만들어 리턴하는 문제이다. 

 

단순히 생각해보면 큰 숫자가 무조건 앞에올수록 숫자는 커진다. 

따라서 numbers를 정렬하고 그 순서대로 붙여서 문자열을 만들자고 생각했다. 

 

그래서 sort에 필요한 compare함수만 작성하면 해결이었다. 

 

두 숫자를 문자열로 만들어 붙인 값

string sa=to_string(a);
    string sb = to_string(b);
    return sa+sb > sb+sa;

sa + sb 와 sb+sa 중 전자가 더 크다면 sa 일 때 true가 리턴되어 기준에 맞는 내림차순 정렬을 할 수 있다. 

sa가 앞에 있을 때 더 큰수가 만들어진다는 소리이기 때문이다.

 

for (int i = 0; i < numbers.size(); i++)
    {
        if(maxV<numbers[i])maxV=numbers[i];
        answer += to_string(numbers[i]);
    }
    if(maxV==0)return "0";
    return answer;

정렬 후 다 붙여서  리턴하면 된다.

그런데 전부 0일 경우엔 00000 을 리턴하는 것이 아닌 0을 리턴해야하기 때문에 따로 처리해준다.