문제

Programmers, 가장 큰 수

핵심

• 입력의 크기가 $10^5$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 0 또는 양의 정수가 주어졌을 때, 이어 붙일 수 있는 가장 큰 수를 구해야 한다. 문제를 봤을 때, 직관적으로 그리디 풀이를 생각해 봤다. 정렬하여 가장 큰 수부터 이어 붙이면 되지 않을까? 작은 수를 먼저 이어 붙인다면 가장 큰 수를 만들 수 없다. 위 명제를 참으로 보고 풀다가 빈틈이 있는 걸 발견했다. 3, 30을 비교할 때 303보다 330이 더 크기 때문이다. 비교 함수를 하드코딩 해도 계속 틀리다가 이어 붙였을 때, 더 큰 수를 기준으로 내림차순 정렬하도록 해서 통과했다.
• 한 가지 테스트케이스는 아예 생각조차 못 했는데, 이는 모든 수가 0일 때 가장 큰 수인 0을 반환해야 한다는 것이다. 추가로 C++과 자바의 정렬 기준이 조금 달라 헷갈린 부분도 있었다.

개선

코드

시간복잡도

• $O(N\times log_2N)$

C++

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

string solution(vector<int> numbers) {
    vector<string> nums;
    for (auto e : numbers)
        nums.push_back(to_string(e));
    sort(nums.begin(), nums.end(), [](auto& a, auto& b) {
        return a + b > b + a;
    });
    string answer = "";
    if (nums[0] == "0")
        return "0";
    for (auto e : nums)
        answer += e;
    return answer;
}

Java

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        ArrayList<String> nums = new ArrayList<>();
        for (var e : numbers)
            nums.add(Integer.toString(e));
        nums.sort((a, b) -> (b + a).compareTo(a + b));
        if (nums.get(0).equals("0"))
            return "0";
        StringBuilder sb = new StringBuilder();
        for (var e : nums)
            sb.append(e);
        return sb.toString();
    }
}