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

가장 큰 수

문제 링크

가장 큰 수

분석

정수 배열 numbers가 주어집니다.

배열의 숫자들을 조합하여 만들 수 있는 가장 큰 수를 구합니다.

결과는 문자열로 반환해야 합니다.

문자열로 변환 후 조합했을 때의 크기를 비교하는 방법으로 풀 수 있습니다.
숫자 A와 B가 있을 때 문자열로 형변환을 해준 뒤 A + B와 B + A의 크기를 비교하면 됩니다.

풀이

정렬을 사용한 방법

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

using namespace std;

bool compare(string a, string b)
{
    // 두 문자열을 합쳤을 때 더 큰 순서로 정렬
    return a + b > b + a;
}

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

    vector<string> strNumbers;

    // 숫자를 문자열로 변환하는 반복문
    for (int num : numbers)
    {
        strNumbers.push_back(to_string(num));
    }

    // 정렬 (사용자 정의 비교 함수 사용)
    sort(strNumbers.begin(), strNumbers.end(), compare);

    // 정렬된 결과를 하나의 문자열로 합치는 반복문
    for (string num : strNumbers)
    {
        answer += num;
    }

    // "00..."의 경우 "0"으로 출력 (예외 처리)
    if (answer[0] == '0')
    {
        answer = "0";
    }

    return answer;
}

1. 모든 숫자를 문자열로 형변환합니다.
2. 문자열을 기준으로 조합했을 때 a가 더 큰 수일 경우 왼쪽으로 위치하게 정렬했습니다. (내림차순)
3. 정렬된 순서대로 문자열을 합쳐서 결과를 반환합니다.
4. 문자열의 맨 앞이 “0”일 경우 문자열이 “0” 한 글자만 가지도록 예외 처리를 해주었습니다.

성능 요약

시간 복잡도는 $O(N \ log \ N)$입니다.

• 숫자를 문자열로 변환하는 반복문 $O(N)$
• 정렬 함수 $O(N log N)$
• 정렬 함수의 문자열 비교 $O(8 \approx 1)$
  • 숫자 하나에 최대 4자리, 숫자를 더한 경우 8자리의 비교
• 정렬된 결과를 하나의 문자열로 합치는 반복문 $O(N)$
• $O(N + N \ log \ N + 1 + N)$

공간 복잡도는 $O(N)$입니다.

• 숫자를 문자열로 형변한 값을 저장하는 strNumbers $O(N)$
• 결과값을 저장하는 answer $O(N)$
• $O(N + N)$

테스트 1 〉 통과 (61.22ms, 9.74MB)
테스트 2 〉 통과 (39.83ms, 6.67MB)
테스트 3 〉 통과 (111.27ms, 10.5MB)
테스트 4 〉 통과 (1.54ms, 4.16MB)
테스트 5 〉 통과 (55.33ms, 7.66MB)
테스트 6 〉 통과 (69.27ms, 7.2MB)
테스트 7 〉 통과 (0.03ms, 4.28MB)
테스트 8 〉 통과 (0.03ms, 4.44MB)
테스트 9 〉 통과 (0.02ms, 4.28MB)
테스트 10 〉 통과 (0.02ms, 4.21MB)
테스트 11 〉 통과 (0.04ms, 3.88MB)
테스트 12 〉 통과 (0.01ms, 4.14MB)
테스트 13 〉 통과 (0.02ms, 4.16MB)
테스트 14 〉 통과 (0.02ms, 3.75MB)
테스트 15 〉 통과 (0.01ms, 3.73MB)