프로그래머스 - 가장 큰 수

프로그래머스 - 가장 큰 수
처음 문제를 보자마자 든 생각은 Combination을 이용해서 모든 조합을 확인하는 것이었다.
실제로 그렇게 구현을 했고, 다음과 같은 Combination을 사용했다.

int orders[100000];
int visit[100000];
long long max = -1;
string max_string = "";
void combination(int n, int r, int depth, const vector<int> numbers)
{
    if(depth == n) {
        string tmp = "";
        if(tmp.compare(max_string) > 0) 
            max_string = tmp;
                
        return;
    }
    
    for(int i=0;i<n;i++) {
        if(visit[i] == 0) {
            visit[i] = 1;
            orders[depth++] = i;
            combination(n, r, depth, numbers);
            visit[i] = 0;
            depth--;
        }
    }
}

string solution(vector<int> numbers) {
	...
}

문제는 이렇게 하니 테스트 케이스는 맞을지라도 채점을 하니 거의 모든 경우에서 시간초과가 걸렸다;;

그래서 고민하다가 떠오른 방법은 다음과 같다.
"[6, 2, 10]" 을 기수정렬처럼 마치 정렬을 하는 것이다.
6과 2를 비교하면 6이 앞으로, 2와 10을 비교하면 2가 앞으로의 느낌으로...

sort를 사용해서 직접 comp 함수 작성했다.
처음에 직접 기수정렬을 짜겠다고 코너케이스 막 복잡하게 구현하다가 피 봤는데, 삽질하다보니 그럴 필요가 없다는 것을 깨달았다.

[a1, a2, a3, a4, a5, ..., an] 이 있다고 가정하고 가장 큰 문자열을 찾을 때, 문제를 쪼개보자.

[a1, a2, a3, a4] 의 집합과 [a5, ..., an] 의 집합으로 나누자.
그 후 [a1, a2][a3, a4] [a5, ..., an]의 집합으로 나눈다.
먼저 첫 째 집합인 [a1, a2]에서 가장 큰 문자열을 찾으려면 "a1a2" 이랑 "a2a1" 을 비교하여 더 큰 문자열을 만들 수 있도록 정렬을 해주면 된다.

이를 정렬 과정에서 재귀적으로 생각해보면 comp 함수를 굳이 복잡하게 작성할 필요가 없다.

따라서 다음과 같은 코드를 얻을 수 있다.

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

using namespace std;

bool comp(const string a, const string b)
{
    return a + b > b + a;
}
// (1) 아래 compare 함수를 사용하면 segfault가 발생하는데 이유를 모르겠다; to_string 문제인 것 같다.
bool compare(const int a, const int b) {
    if(a == b)
        return true;
    
    string p = to_string(b);
    string q = to_string(a);
    string pq = p + q;
    string qp = q + p;
    
    if(pq.compare(qp) > 0)
        return false;
    
    return true;
}
string solution(vector<int> numbers) {
    string answer = "";
    int size = numbers.size();
    
    vector<string> num_to_string;
    for(int i=0;i<numbers.size();i++) 
        num_to_string.push_back(to_string(numbers[i]));
    sort(num_to_string.begin(), num_to_string.end(), comp);
    for(auto i : num_to_string) 
        answer += i;
        
    // 주석(1) 참조
    /*sort(numbers.begin(), numbers.end(), compare);
    for(auto i : numbers) 
        answer += to_string(i);*/

    if(answer[0] == '0') // 11번 케이스 예외처리
        answer = "0";
    
    return answer;
}