[Lv2] 가장 큰 수 (정렬)

해당 문제 해결 전 정렬에 대해서 알고싶으신 분들은 아래 포스팅 참고해주시면 됩니다.

C++ 정렬 알고리즘 총정리: 버블·퀵·합병·std::sort 비교

버블 정렬, 퀵 정렬, 합병 정렬, 그리고 C++ 표준 라이브러리 std::sort를 비교해보며 각 알고리즘의 특징과 장단점을 정리합니다. 알고리즘 공부를 위한 기초부터 실무에서 가장 많이 쓰이는 정렬 함수까지 한눈에 확인할 수 있습니다.

Gibeom KimGibeom Kim

문제

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

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

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

제한 사항

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

입출력 예

풀이

핵심 아이디어는, 숫자를 이어 붙였을 때 큰 숫자가 먼저 나오도록 정렬을 하는 것이다. 가장 간단히 구현하는 방법은 입력값을 std::string으로 바꾼 다음 두 값을 각각 a, b라 했을 때, a + b와 b + a 를 이어 붙여서 더 큰 값이 앞에 오도록 정렬을 하는 방법이다. 예를 들자면 다음과 같다.

• "6" + "10" = "610"
• "10" + "6" = "106"

"610" > "106" → "6"이 "10"보다 앞에 와야 한다.

코드

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

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

    std::vector<std::string> num_strings{};
    num_strings.reserve(numbers.size());

    // 숫자를 문자열로 변환
    for (const auto num : numbers)
    {
        num_strings.push_back(std::to_string(num));
    }

    // 정렬을 위한 비교함수. 
    auto compare = [](const std::string &a, const std::string &b)
    {
        return a + b > b + a; // 내림차순
    };

    // std::sort를 사용하여 정렬 
    std::sort(num_strings.begin(), num_strings.end(), compare);

    // 모든 수가 0이면, 0을 반환하도록 한다. 
    if (num_strings.front() == "0")
    {
        return "0";
    }

    // 각각의 배열에 있는 문자열을 하나의 문자열로 합치
    for (const auto &string : num_strings)
    {
        answer += string;
    }

    return answer;
}