프로그래머스 - 가장 큰 수 (Level2, Sorting) C++

우선 정렬 알고리즘에 관한 문제이고 문제는 아래와 같다.

 

우선 문제를 간단하게 분석해보자면, numbers의 길이가 100,000이기 때문에 단순히 for문을 사용하거나 문자열로 나타내기 위해 단순히 문자열의 순열 (next_permutation) 방식으로는 시간 초과가 날 것이라 생각했다.

 

100,000의 길이면 nlogn 시간 복잡도를 가진 정렬을 상한선으로 택해야 하는데, C++에서 의 sort() 함수의 시간 복잡도가 nlogn이기 때문에 해당 sort() 함수를 잘 이용해보면 될 것이라 생각했다.

 

sort 함수를 기존 정렬 방식이 아닌 주어진 문제에 맞는 정렬 방식을 사용하고 싶다면 sort 의 3번째 파라미터에 정렬 조건에 대한 비교 함수를 넣으면 자신이 원하는 정렬을 수행 가능하기 때문에 nlogn 시간 복잡도를 유지하면서 커스텀을 할 수 있다는 것을 알고 있었다.

주어진 입출력의 예를 한번 살펴보면,

[3, 30, 34, 5, 9] 에서 가장 큰 수가 되려면 9534330인데, 정렬 시 두 개의 값에 대해서 어떤 식으로 비교를 해야 가장 큰 수로 정렬이 가능할지 생각해보니 아래와 같았다.

 

3,30 -> 330, 303 비교했을 때 330이 더 크기 때문에 두 수를 a, b로 가정하면 a + b > b + a 일 때 참인 경우이다.

좀 더 이해하기 쉽도록 플로우를 구성해보면,,

 

3, 30 -> 330이 더 크기 때문에 그대로 유지

30, 34 -> 3430이 더 크기 때문에 스위칭

30, 5 -> 530이 더 크기 때문에 스위칭

30, 9 -> 930이 더 크기 때문에 스위칭,, 여기까지 했을 때 -> [3,34,5,9,30] 이렇게 정렬이 될 것이다. 아무튼 비교 함수를 a + b > b + a로 만들었을 때 결국에는 [9, 5, 34, 3, 30]로 정렬될 수 있다. + 만약 정렬 시 가장 앞에 오는 수가 0일 경우에는 0으로 return 되어야 한다.

 

이런 생각을 바탕으로 작성한 코드는 아래와 같다.

// numbers의 길이가 100,000 -> 시간 복잡도 nlogn으로 풀어야 할듯
// algorithm sort() 함수가 nlogn 시간 복잡도를 지님

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

using namespace std;

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

string solution(vector<int> numbers) {

    string answer = ""; 

    vector<string> tmp(numbers.size());

    for(int i = 0; i < numbers.size(); i++){
        tmp[i] = to_string(numbers[i]);
    }

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

    if(tmp[0] == "0") answer = "0";
    else{
        for(int i = 0; i < tmp.size(); i++){
           answer += tmp[i]; 
        }
    }

    return answer;
}