[Programmers] 42746번 - 가장 큰 수 [Java][C++]

문제 링크

---

1. 문제 풀이

numbers의 길이가 최대 100,000이라서 주어진 정수들을 이어 붙인 모든 조합을 찾는 방식으로는 해결할 수 없다. 이 문제는 정렬을 활용하면 해결할 수 있는데 numbers의 임의의 두 수 num1, num2에 대해 num1 뒤에 num2를 붙인 수와 num2 뒤에 num1을 붙인 수를 비교해 전자가 크면 num1이 앞에 오도록, 후자가 크면 num2가 앞에 오도록 정렬하면 정렬된 결과를 순서대로 이어 붙였을 때 numbers를 재배치해서 얻을 수 있는 가장 큰 수가 된다.(동일하면 두 수가 같은 경우라 어떻게 정렬해도 상관없다.)

numbers의 원소는 0일 수 있기 때문에 numbers 가 [0, 0]일 경우 "00"이 아니라 "0"을 리턴해야 함에 유의해야 한다.(테스트 11)

---

2. 코드

1. 풀이 [Java]

두 수 num1, num2에 대해 num1 뒤에 num2를 붙인 것과 num2 뒤에 num1을 붙인 것은 길이가 동일하다. Java에서 동일한 길이의 숫자로 이루어진 문자열의 정렬 기준은 그냥 숫자일 때랑 동일하다.

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] arr = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            arr[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

        String ans = String.join("", arr);

        if (ans.charAt(0) == '0') {
            return "0";
        } else {
            return ans;
        }
    }
}

2. 풀이 [C++]

두 수 num1, num2에 대해 num1 뒤에 num2를 붙인 것과 num2 뒤에 num1을 붙인 것은 길이가 동일하다. C++에서 동일한 길이의 숫자로 이루어진 문자열의 정렬 기준은 그냥 숫자일 때랑 동일하다.

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

using namespace std;

string solution(vector<int> numbers) {
    vector<string> v;
    for (int n : numbers) v.push_back(to_string(n));
    sort(v.begin(), v.end(), [](const string& a, const string& b) {
        return b + a < a + b;
    });

    string ans;
    for (string& s : v) ans += s;

    if (ans.front() == '0') {
        return "0";
    } else {
        return ans;
    }
}

---