가장 큰 수(프로그래머스)

정렬 조건을 정하여 정렬하는 문제이다.

 

위 설명처럼 순열을 모두 구해서 내림차순으로 정렬하는 방법을 생각해 볼 수 있다. 값은 정확하게 나오지만 순열의 개수는 (numbers의 원소의 개수)! (팩토리얼)이기 때문에 원소의 갯수가 많을수록 기하급수적으로 많아진다. 결국 시간 초과가 되므로 이 방법은 쓸 수 없다.

(STL에서 제공하는 next_permutation을 사용하면 순열을 쉽게 구할 수 있으므로 한번 시도해보는 것도 나쁘지 않다)

 

정렬을 내림차순으로 하더라도 [6, 10, 2] 같은 경우 [10, 6, 2]로 1062가 되므로 가장 큰 수를 만족하지 못한다. 하지만 원소들을 string으로 바꾸고 서로의 조합을 통해 비교해서 정렬하면 어떨까?

 

예를 들어 [6, 10, 2]가 있다면 이를 string으로 바꾼다. ["6", "10", "2"] 이제 정렬을 해보자. 우선 "6"과 "10"의 정렬 작업을 한다. 그냥 서로를 비교해서 정렬하면 위와 다를 것이 없다. 하지만 서로 조합하면 어떨까? "6"+ "10"은 "610"이다. 반대로 "10" + "6"은 "106"이다. 이 둘을 비교해보면 "610"이 더 크다는 것을 알 수 있다. 그러면 numbers는 그대로 ["6", "10", "2"]가 될 것이다. 이제 "10"과 "2"에 대해 정렬 작업을 한다. "10"+ "2"은 "102"이다. 반대로 "2" + "10"은 "210"이다. "210"이 더 크기 때문에 numbers는 정렬 작업을 통해 ["6", "2", "10"]이 된다. 이 배열의 원소들을 차례대로 answer에 더해주면 "6210"으로 가장 큰 수가 만들어 진다.

 

하지만 한가지 경우를 생각해야 한다. 바로 정렬한 맨 앞 원소의 첫번째 문자가 0인 경우이다. 이 경우에는 answer에 직접 "0"을 대입해주면 된다. 

 

코드는 다음과 같다.

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

using namespace std;

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

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> temp;

    for (auto num : numbers) {
        temp.push_back(to_string(num));
    }

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

    for (auto str : temp) {
        answer += str;
    }

   if (temp[0] == "0") answer = "0";

    return answer;
}