프로그래머스 42746 - 가장 큰 수 (Lv.5)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/42746

// 프로그래머스 42746 - 가장 큰 수 (Lv.5)
// https://school.programmers.co.kr/learn/courses/30/lessons/42746

// 문제 설명
// 0 또는 양의 정수가 담긴 배열 numbers가 주어진다.
// 이 수들을 이어 붙여 만들 수 있는 가장 큰 수를 문자열로 반환하라.
// [6, 10, 2]라면 6210, 62103, 6102, ... 중 가장 큰 "6210".

// 제약 조건
// 1 <= numbers 길이 <= 100,000
// 0 <= numbers 원소 <= 1,000
// 정답이 매우 클 수 있으므로 문자열로 반환한다.

// Example
// Input : [6, 10, 2]            Output: "6210"
// Input : [3, 30, 34, 5, 9]     Output: "9534330"

// 접근 — 두 수의 순서만 정하는 비교자 a+b > b+a로 정렬
// 순열을 다 만들면 100,000!. 대신 "인접한 두 수의 앞뒤만 최적이면 전체가 최적"이라는
// 국소 교환 논증을 쓴다. a를 앞에 둘지 b를 앞에 둘지는 이어 붙인 문자열
// a+b와 b+a를 사전순 비교한 결과와 같다(길이가 같으므로 사전순 = 수의 크기 비교).
// 1) 각 수를 문자열로 바꾼다. 자릿수가 다른 수를 그냥 사전순 정렬하면
//    "3" < "30"이 되어 3을 뒤로 보내는데, 실제로는 "330" > "303"이라 3이 앞이어야 한다.
//    이어 붙인 결과로 비교해야 자릿수 차이가 자동으로 흡수된다.
// 2) sort(v, cmp)로 내림차순 배치 후 전부 이어 붙인다.
// 3) 전부 0이면 "000...0"이 되므로 첫 글자가 '0'일 때 "0"으로 정규화한다.
//    내림차순이므로 첫 글자가 '0'이면 나머지도 모두 0이다.
// 시간 O(n log n * L) (L = 최대 자릿수 4), 공간 O(n * L)

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

using namespace std;

bool cmp(const string& a, const string& b)
{
    return a + b > b + a;
}

string solution(vector<int> numbers)
{
    vector<string> v;
    v.reserve(numbers.size());

    for (int n : numbers)
        v.push_back(to_string(n));                 // 비교 단위를 수에서 문자열로 바꿈

    sort(v.begin(), v.end(), cmp);

    string answer;
    for (const string& s : v)
        answer += s;

    if (answer[0] == '0')                          // 전부 0인 입력 정규화
        return "0";

    return answer;
}

정리

• 커리큘럼 103번. 정렬 문제로 분류되지만 실제 난이도는 비교 기준을 발견하는 데 있다. 전체 순열은 100,000!이라 완전 탐색이 불가능하고, “무엇을 기준으로 정렬하면 이어 붙인 결과가 최대가 되는가” 한 줄이 풀이의 전부다. 크기순·자릿수순·첫 글자순 모두 반례가 있고, 정답은 “두 수를 이어 붙여 비교한다” — a + b > b + a.
• 왜 그 비교자가 옳은가는 국소 교환 논증으로 본다. 최적 배치에서 인접한 두 수 a, b를 뒤집었을 때 더 커지는 경우가 없어야 하고, 인접 교환은 앞뒤 문맥과 무관하게 a+b vs b+a만 바꾼다. 즉 “인접쌍이 모두 최적”이 곧 전체 최적이고, 그런 순서를 만들어 주는 것이 정렬이다. 정렬로 푸는 그리디의 정당성은 대부분 이 형태로 검증된다(1931 회의실 배정의 끝나는 시각 기준과 같은 계열).

• 사전순 정렬을 그대로 쓰면 틀리는 이유는 자릿수가 다르면 사전순과 수의 크기가 어긋나기 때문이다. "3" < "30"이지만 "330" > "303"이라 3이 앞에 와야 한다. 이어 붙인 두 문자열은 길이가 항상 같아서(둘 다

  a

  +

  b

  ) 그 안에서는 사전순 = 수 크기 비교가 성립한다 — 길이를 맞춰 놓고 비교한다는 게 이 트릭의 정체.

• 비교자에 등호를 넣어 >=로 쓰면 안 된다. sort는 비교자가 strict weak ordering(특히 cmp(x, x) == false)임을 요구하는데 >=는 자기 자신에 true를 반환해 전제가 깨지고, 범위를 벗어난 읽기로 이어지는 미정의 동작이 된다. 중복 원소가 있는 입력에서만 터지므로 예제만 돌려서는 발견되지 않는 함정. 비교자는 항상 strict(< 또는 >)로 쓴다.
• 마지막 answer[0] == '0' 한 줄은 [0, 0, 0] 같은 입력을 위한 것이다. 그냥 이어 붙이면 "000"이 되는데 답은 "0"이다. 내림차순 정렬이므로 선두가 0이면 나머지도 전부 0 — 조건 한 번으로 끝난다. 원소 상한이 1,000이라 문자열 길이는 최대 4, 결과 길이는 최대 400,000자로 int 인덱스 범위에 여유가 있다.
• 복잡도는 O(n log n)에 문자열 결합 상수가 붙어 O(n log n · L), L ≤ 4. 비교마다 임시 문자열 2개가 생기므로 비교자 인자를 const string&으로 받아 복사를 줄였고, reserve로 벡터 재할당을 없앴다. 실측 10만 개 랜덤 입력 30~40ms.
• 검증: 예제 2개(“6210”, “9534330”)와 경계 케이스 — 전부 0 [0,0,0](→ “0”), 원소 1개 [0]·[1000], 접두 함정 [30,3](→ “330”)·[9,90,900](→ “990900”), 중복 [1,1,1], 상한 10만 개 성능(30~40ms) 통과 (MSVC /std:c++17 /O2 컴파일·실행).

핵심 요약 — 이어 붙여 최대를 만드는 문제는 순열(100,000!)이 아니라 a + b > b + a 비교자 정렬로 O(n log n)에 끝난다. 이어 붙인 두 문자열은 길이가 같아 그 안에서는 사전순 = 수 크기가 되고, 인접 교환 논증이 정렬의 정당성을 보장한다. 비교자에 등호(>=)를 넣으면 중복 원소에서 미정의 동작, 전부 0인 입력은 "0"으로 정규화해야 한다.