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

🖊️ 문제

가장 큰 수  

 

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

🖥️ 코드

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

using namespace std;

bool cmp(const string& a, const string& b)
{
    string c = a + b;
    string d = b + a;

    return c > d;
}

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

    for (int i = 0; i < numbers.size(); i++)
        v.push_back(to_string(numbers[i]));

    sort(v.begin(), v.end(), cmp);

    for (int i = 0; i < numbers.size(); i++)
        answer += v[i];

    if (v[0] == "0")
        return "0";

    return answer;
}

 

🤔 나의 생각

앞자리가 가장 큰 수일 수록 앞에 와야 한다는 규칙은 바로 알았으나.. 3과 30의 비교 3과 31, 30과 300 등.. 여러 경우의 수가 많아서 골머리를 앓았다.

 

분기가 많아져 코드가 지저분해졌고 이렇게 푸는 게 맞나?라는 의구심이 들었다.

무언가 규칙이 있을 것 같아서 계속 종이에 적다가 규칙을 찾았는데, 원소 두 개를 뽑아 순열을 만들고 큰 수를 만드는 숫자를 앞으로 정렬하면 답이 나온다!

예를 들어 벡터 {300, 30}이 있을 때, 이 둘로 만들 수 있는 순열은 30300과 30030이다. 이때 30을 앞에 배치했을 때 큰 수를 만들 수 있으니 {30, 300}으로 벡터를 정렬하면 정답인 30300을 쉽게 파싱 할 수 있다.