주어진 숫자들을 재배열하여 가장 큰 수 만들기 – C++ 구현 방법

이 글에서는 주어진 숫자들을 재배열하여 가장 큰 수를 만드는 방법을 알아봅니다. 예를 들어 {45, 74, 23}이라는 숫자들이 주어졌을 때, 프로그램은 이를 조합하여 가장 큰 수인 744523을 찾아냅니다. 여기서 핵심은 각 자릿수를 개별적으로 배열하는 것이 아니라, 숫자 전체를 하나의 단위로 배치한다는 점입니다.

이 문제는 문자열 정렬(string sorting)을 활용하면 효율적으로 해결할 수 있습니다. 다만 일반적인 정렬과 달리 비교 로직이 다릅니다. 비교 함수는 두 숫자 a와 b를 입력받아 이어 붙인 ab와 ba를 생성한 뒤, 둘 중 어느 쪽이 더 큰지를 기준으로 정렬 순서를 결정합니다.

알고리즘

compareStrings(a, b)

begin
    ab := b에 a를 이어 붙임
    ba := a에 b를 이어 붙임
    ba와 ab를 비교하여, ba가 더 크면 1을 반환하고 그렇지 않으면 0을 반환
end

getLargest(arr)

begin
    compareString()의 비교 로직을 사용해 arr을 정렬
    arr의 각 문자열 s에 대해
        s를 출력
    반복 종료
end

예제 코드

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int stringCompare(string a, string b) {
    string ab = a.append(b);
    string ba = b.append(a);
    return ab.compare(ba) > 0 ? 1 : 0;
}
void getLargest(vector<string> arr) {
    sort(arr.begin(), arr.end(), stringCompare); // 배열 정렬
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i];
}
int main() {
    vector<string> arr;
    arr.push_back("45");
    arr.push_back("74");
    arr.push_back("23");
    getLargest(arr);
}

실행 결과

744523

위 코드에서 stringCompare 함수는 두 숫자를 서로 다른 순서로 이어 붙여 더 큰 조합을 앞쪽에 오도록 정렬합니다. 이렇게 하면 74, 45, 23 순으로 정렬되어 최종적으로 744523이라는 가장 큰 수가 출력됩니다. 이 방법은 숫자의 개수나 자릿수가 달라도 동일하게 적용할 수 있는 범용적인 해결책입니다.