코딩테스트 : 가장 큰 수

해당 문제는 주어진 숫자들을 이용해 만들 수 있는 가장 큰 수를 만드는 문제로 앞 자리가 클 수록 앞에 배치하면 되는 문제이다.

해당 부분은 복잡하게 느껴질 수 있지만, 문자열로 단순히 생각하면 쉽게 해결할 수 있다.

문자열을 정렬 시키면 가장 앞에 문자부터 비교하며 같다면 다음 문자끼리 비교하는 식으로 정렬한다. 그렇다면 숫자를 문자열로 바꾼다면 어떻게 정렬이 되겠는가

[3,30,34,5,9]를 내림차순으로 정렬시킨다면 9 5 34 30 3으로 정렬된다. 하지만 가장 큰 수를 만드려면 9 5 34 3 30 으로 정렬이 되야한다.

때문에 내림차순으로 정렬하며 커스텀 함수를 sort에 넣어줘서 3, 30을 정렬할 때 사전순으로 더 큰 수를 뽑아야한다.(ex. 303 < 330)

 

Sort에 대한 자세한 내용은 아래 블로그에서 확인할 수 있다.

Sort(정렬)

 

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

using namespace std;

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> v;
    
    //int 배열을 string 배열로 변환
    for(int i : numbers)
    {
		    //string 문자열로 만들어주는 함수
        v.push_back(to_string(i));
    }
    //두 문자열을 더했을 때 사전 순으로 더 큰 순서대로 정렬한다. (ex. 9, 5 : 95 > 59)
    sort(v.begin(), v.end(), [](string str1, string str2){
        return str1 + str2 > str2 + str1;
    });
    
    //정렬한 v에 문자열을 answer에 다 넣어준다.
    for(string str : v)
    {
        answer += str;
    }
    
    //만약 answer가 전부 0으로 이루어져있다면 00000000... 이 아닌 0을 반환한다.
    if(answer == string(answer.length(), '0'))
        return "0";
    
    return answer;
}