[C++][정렬] 프로그래머스 - 가장 큰 수

 

 

1. 문제

우선 수들을 조합해서 가장 큰 수를 만드는 문제이다.

 

최초에는 당연히 next_permutation을 사용해서 풀어보았다

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

using namespace std;

string solution(vector<int> numbers) {
    string answer = "";
    
    vector<int> tmp;
    sort(numbers.begin(), numbers.end());
    
    do {
        string s = "";
        for(auto it = numbers.begin(); it != numbers.end(); ++it) {
            s += to_string(*it);
        }
        tmp.push_back(stoi(s));
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    sort(tmp.begin(), tmp.end(), greater<>());
    
    answer = to_string(*tmp.begin());
    
    return answer;
}

하지만 이 방법으로는 너무 큰 수가 만들어져 core dump 오류가 났다.

이에 tmp를 string으로 유지하며 해결해 보았다.

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

using namespace std;

string solution(vector<int> numbers) {
    string answer = "";
    
    vector<string> tmp;
    sort(numbers.begin(), numbers.end());
    
    do {
        string s = "";
        for(auto it = numbers.begin(); it != numbers.end(); ++it) {
            s += to_string(*it);
        }
        tmp.push_back(s);
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    sort(tmp.begin(), tmp.end());
    
    answer = tmp[tmp.size() - 1];
    
    return answer;
}

이번에는 시간초과가 무수히 떨어졌다.

 

next_permutation은 O(n)인데, numbers의 길이가 최대 10만이고, 내부의 for문과 sort까지 생각해 보았을 때 절대 시간 내에 들어올 수 없는 풀이였다.

 

모든 경우의 수를 해보지 않으려면?
기가막힌 정렬 함수를 만들어서 한 번의 정렬로 끝내보자.

 

[3, 30, 34, 5, 9]

이렇게 있을 때,

3, 30을 더하면 330, 303이 나온다. 그러므로 3이 30보다 앞에 와야 한다. 이걸 비교함수로 만들면?

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

using namespace std;

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

string solution(vector<int> numbers) {
    string answer = "";
    
    vector<string> tmp;
    
    for(int i=0; i<numbers.size(); i++) {
        tmp.push_back(to_string(numbers[i]));
    }
    
    sort(tmp.begin(), tmp.end(), compare);
    
    for(int i=0; i<tmp.size(); i++) {
        answer += tmp[i];
    }
    
    return answer;
}

그런데

하나가 틀렸다....!

 

tmp 정렬시, 가장 우선순위를 가진 숫자, 즉 tmp[0] == 0이라면, 뒤에 숫자가 붙지 않고 그냥 0이 반환되어야 한다.

이 예외를 생각하는데 굉장히 오래걸렸다....

 

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

using namespace std;

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

string solution(vector<int> numbers) {
    string answer = "";
    
    vector<string> tmp;
    
    for(int i=0; i<numbers.size(); i++) {
        tmp.push_back(to_string(numbers[i]));
    }
    
    sort(tmp.begin(), tmp.end(), compare);
    
    for(int i=0; i<tmp.size(); i++) {
        answer += tmp[i];
    }
    
    if(tmp[0] == "0") return "0";
    else return answer;
}

이렇게 하니 정답이 나왔다!

 

교훈: 시간복잡도 계산을 잘 하고, 예외 케이스 생각을 잘하자