[Algorithm] C++ 백준 16496번: 큰 수 만들기

문제 정보

문제: https://www.acmicpc.net/problem/16496
요약: 음이 아닌 정수 N개를 배열하여 만들 수 있는 가장 큰 수를 구합니다. 수는 공백으로 구분되고, 1,000,000,000 이하의 음이 아닌 정수입니다. 0을 제외한 나머지 수는 0으로 시작하지 않습니다.
제한: N ≤ 1,000, 각 수 ≤ 1,000,000,000, 시간 2초, 메모리 512MB

입출력 형식/예제

1
2
3
4
5
6
입력 예시 1
5
3 30 34 5 9

출력 예시 1
9534330

접근 개요(아이디어 스케치)

핵심 관찰: 두 수 a와 b를 배열할 때, a+b와 b+a를 비교하여 더 큰 쪽을 앞에 배치합니다. 예를 들어 “3"과 “30"의 경우 “330” > “303"이므로 “3"을 앞에 배치합니다.
그리디 선택: 이 비교 함수로 모든 수를 정렬하고, 앞에서부터 순서대로 이어붙입니다.
엣지 케이스: 모든 수가 0이면 “0"을 출력하고, 그렇지 않으면 결과 그대로 출력합니다.
시간 복잡도: 정렬 O(N log N × L), 여기서 L은 문자열 비교 비용입니다.

알고리즘 설계

비교 함수: compare(a, b) = (a + b > b + a). 이 함수는 전이적(transitive) 성질을 만족합니다.
정렬: sort 함수에 커스텀 비교자를 적용하여 문자열 벡터를 정렬합니다.
연결: 정렬된 문자열들을 순서대로 이어붙여 결과 문자열을 생성합니다.
0 처리: 결과 문자열의 첫 문자가 ‘0’이면 “0"만 출력합니다.

올바름 근거(요지)

비교 함수의 전이성: compare(a, b)가 true이고 compare(b, c)가 true이면, compare(a, c)도 true입니다. 이는 수학적으로 증명 가능하며, 정렬의 정확성을 보장합니다.
그리디 선택 성질: 각 위치에서 국소적으로 최적의 선택(가장 큰 연결 결과를 만드는 배치)이 전역 최적해를 도출합니다.
정당성: 어떤 두 인접한 수의 배치 순서를 바꾸면 결과가 더 작아지므로, 정렬된 배열의 순서대로 이어붙인 결과가 최대값입니다.

복잡도

시간: O(N log N × L), 여기서 N은 수의 개수, L은 평균 문자열 길이입니다.
공간: O(N × L), 문자열 벡터 저장 공간

구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

// 사용자 정의 비교 함수: 두 문자열을 이어붙였을 때 더 큰 값을 만드는 순서로 정렬
bool compare(const string &a, const string &b) {
    return a + b > b + a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<string> numbers(n);
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }
    
    // 커스텀 비교 함수로 정렬
    sort(numbers.begin(), numbers.end(), compare);
    
    // 결과 문자열 생성
    string result = "";
    for (const string &num : numbers) {
        result += num;
    }
    
    // 모든 숫자가 0인 경우 처리 (예: 0, 0, 0 -> "000"이 아닌 "0" 출력)
    if (result[0] == '0') {
        cout << "0\n";
    } else {
        cout << result << "\n";
    }
    
    return 0;
}

코드 설명

헤더 및 입력:
- #include <bits/stdc++.h>로 표준 라이브러리 포함
- Fast I/O 설정으로 입출력 속도 향상
- n과 n개의 숫자를 문자열 배열에 저장
비교 함수:
- a + b와 b + a를 문자열 연결로 비교합니다.
- 결과가 더 크면 a를 앞에 배치합니다.
정렬:
- sort 함수와 커스텀 비교자 compare를 사용하여 정렬합니다.
결과 생성:
- 정렬된 순서대로 모든 문자열을 이어붙입니다.
엣지 케이스 처리:
- 결과 문자열의 첫 문자가 ‘0’이면 (모든 숫자가 0인 경우), “0"만 출력합니다.