[프로그래머스] 42746번 - 가장 큰 수 [Java][C++]

문제 링크

---

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

---

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

---

입출력 예

numbers	return
[6, 10, 2]	“6210”
[3, 30, 34, 5, 9]	“9534330”

---

1. 문제 풀이

주어진 정수들을 이어 붙였을 때 만들 수 있는 가장 큰 수를 출력하는 문제로 정수의 개수가 최대 100,000 개라서 모든 조합을 찾는 방식으로는 해결할 수 없다. 해당 문제는 정렬을 활용하면 해결할 수 있는데 두 수 num1, num2 에 대해 num1 뒤에 num2 를 붙이는 것과 num2 뒤에 num1 을 붙이는 것을 비교해서 전자가 더 크면 num1 이 앞에 오도록, 후자가 더 크면 num2 가 앞에 오도록 정렬한 후 순서대로 이어붙여서 출력하면 된다.

주어진 정수는 0 일 수 있어서 numbers 가 [0, 0] 일 경우 "00" 이 아니라 "0" 을 리턴해야 함에 유의해야 한다.(테스트 11)

---

2. 코드

1. 정렬 [Java]

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

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 answer = String.join("", arr);

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

2. 정렬 [C++]

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

#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[0] == '0') {
        return "0";
    } else {
        return ans;
    }
}

---

3. 풀이 정보

1. 정렬 [Java]

정확성 테스트
테스트 1 〉 통과 (144.18ms, 123MB)
테스트 2 〉 통과 (77.63ms, 120MB)
테스트 3 〉 통과 (187.47ms, 151MB)
테스트 4 〉 통과 (11.13ms, 83.8MB)
테스트 5 〉 통과 (138.85ms, 122MB)
테스트 6 〉 통과 (134.93ms, 129MB)
테스트 7 〉 통과 (1.91ms, 76.2MB)
테스트 8 〉 통과 (1.95ms, 85MB)
테스트 9 〉 통과 (1.75ms, 88.9MB)
테스트 10 〉 통과 (1.76ms, 85.9MB)
테스트 11 〉 통과 (2.12ms, 77.8MB)
테스트 12 〉 통과 (1.56ms, 85.2MB)
테스트 13 〉 통과 (1.41ms, 83.2MB)
테스트 14 〉 통과 (1.75ms, 99.1MB)
테스트 15 〉 통과 (1.73ms, 83.2MB)

2. 정렬 [C++]

정확성 테스트
테스트 1 〉 통과 (56.00ms, 9.84MB)
테스트 2 〉 통과 (34.33ms, 6.73MB)
테스트 3 〉 통과 (60.62ms, 10.6MB)
테스트 4 〉 통과 (1.94ms, 4.2MB)
테스트 5 〉 통과 (41.77ms, 7.69MB)
테스트 6 〉 통과 (35.64ms, 7.13MB)
테스트 7 〉 통과 (0.02ms, 4.21MB)
테스트 8 〉 통과 (0.02ms, 4.01MB)
테스트 9 〉 통과 (0.02ms, 4.21MB)
테스트 10 〉 통과 (0.02ms, 3.68MB)
테스트 11 〉 통과 (0.02ms, 4.14MB)
테스트 12 〉 통과 (0.02ms, 4.12MB)
테스트 13 〉 통과 (0.01ms, 4.12MB)
테스트 14 〉 통과 (0.02ms, 3.86MB)
테스트 15 〉 통과 (0.01ms, 4.2MB)

---