[프로그래머스 Lv.2] 가장 큰 수

[문제]

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

 

[풀이]

 

단순하게 모든 조합을 만들어서 풀 수는 없다(시간 초과 발생). 그렇다고 오름차순 정렬로만은 문제를 풀 수 없는데, 예를 들어 6과 10 두 가지 숫자만 입력됐다고 생각해보자.

 

- 6과 10으로 만들 수 있는 조합 : 610, 106

 

당연히 6이 먼저 온 다음, 10이 다음으로 와야 610로 가장 큰 수가 된다. 이를 위해 sort 방식을 만들어줘야하는데, 정말 간단하게 만들 수 있다. 두 값을 인자로 받았을 때, 이걸 string으로 변환하고 바로 비교하면 된다.

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

using namespace std;

bool Compare(int _Left, int _Right)
{
    string L = to_string(_Left);
    string R = to_string(_Right);

    return L + R > R + L;
}

string solution(vector<int> numbers)
{
    string answer = "";

    // 숫자 비교한 뒤, 앞자리가 가장 큰 것을 기준으로 정렬하고 string으로 조합해서 리턴
    // 10 6이 있을 때, 106보단 610이 크다, 1의 자리를 비교해야함
    sort(numbers.begin(), numbers.end(), Compare);
    for (int i = 0; i < numbers.size(); i++)
    {
        answer += to_string(numbers[i]);
    }

    if (answer[0] == '0') return "0";

    return answer;
}