[프로그래머스] 가장 큰 수 c++

 

 

가장 처음 생각해낸 방법은 모든 경우의 수를 나열하고, 그 중 큰 수를 찾는 방법이었다. STL의 next_permutation을 이용해서 모든 순열을 만들어서 비교했다. 하지만 이 경우는 next_permutation메서드의 시간복잡도O(N)과 내부 for문에 걸리는 시간때문에 시간초과가 발생한다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
string solution(vector<int> numbers) {   
 
    sort(numbers.begin(),numbers.end());
    int max_number = 0;
    do{
        string tmp;
        for(int i=0;i<numbers.size();i++){
            tmp += to_string(numbers[i]);
        }
        
        max_number = max(max_number,stoi(tmp));
    }while(next_permutation(numbers.begin(),numbers.end()));
 
    return to_string(max_number);
}

 

따라서 다음과 같이 문자열 두개(3, 21이라고 가정)가 들어왔을 때 321과 213중 321이 더 크므로 3, 21순으로 정렬하도록 만드는  compare함수를 따로 만들어서 STL sort메서드를 재정의해야한다. 

결국 두 수를 비교했을 때 가장 크게 되는 숫자가 맨 앞에 오게 될 것이므로, 문제상황을 해결할 수 있다. 

#include <iostream>
#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> v;
    for(int i=0;i<numbers.size();i++){
        v.push_back(to_string(numbers[i]));
    }
    
    sort(v.begin(),v.end(),compare);
    
    for(int i=0;i<v.size();i++){
        answer += v[i];
    }
    
    if(answer[0]=='0')
        return "0"; 
    return answer;
}