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

• 출처: 프로그래머스 42746
• 분류: 정렬 · Lv.2

문제

0 이상 1000 이하의 정수 배열 numbers가 주어진다. 이 수들을 이어 붙여 만들 수 있는 가장 큰 수를 문자열로 반환한다.

핵심

두 수 a, b를 이어 붙인 “ab”와 “ba”를 비교한다. “ab” > “ba”이면 a가 앞에 와야 한다. 이 비교 함수로 정렬하면 된다.

풀이

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

string solution(vector<int> numbers) {
    vector<string> strs;
    for (int n : numbers)
        strs.push_back(to_string(n));

    sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
        return a + b > b + a;
    });

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

    string answer;
    for (const auto& s : strs)
        answer += s;
    return answer;
}

메모

• 비교 함수 a + b > b + a는 문자열 사전순 비교다. 예: “3”과 “30”이면 “330” > “303”이므로 “3”이 앞에 온다
• 이 비교는 추이성(transitivity)을 만족하므로 sort의 비교 함수로 안전하다
• strs[0] == "0" 체크는 모든 원소가 0인 경우 “000…” 대신 “0”을 반환하기 위한 것이다. 정렬 후 가장 큰 값이 “0”이면 나머지도 전부 “0”이다
• to_string과 문자열 연결(+)에 의한 오버헤드가 있지만, 원소가 최대 1000이므로 문자열 길이가 최대 4자다. 실질적 영향은 없다

복잡도

풀이	시간	공간
커스텀 정렬	O(N log N)	O(N)