프로그래머스 - 가장 큰 수

테스트 케이스는 통과하는데 채점에서는 시간초과 오류가 발생한다.

dfs를 먼저 떠올렸는데 여기서 사용하기에는 적당한 방법이 아닌가보다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int visit[100000];
vector <string> v;
vector <string> v3;
vector <int> v2;
string temp="";
bool Standard(string A, string B)
{
    if (A + B > B + A) return true;
    return false;
}

void dfs(vector <int> n ,int count){
    if(n.size() == count){ // 벡터 사이즈만큼 temp에 순열을 붙인 문자열을 만들게 됐을때
        for(int i=0;i<v.size();i++){
            temp += v[i];
        }
        v3.push_back(temp);
        temp = "";
        return;
    }    
    for(int i =0;i<n.size(); i++){
        if(!visit[i]){ // 조합이 아닌 순열문제다.
         visit[i]=1;
         string k = to_string(n[i]);
         v.push_back(k);
         dfs(n , count+1);
         v.pop_back();
         visit[i]=0;
        }
    }
}

string solution(vector<int> numbers) {
    string answer = "";
    dfs(numbers ,0);
    sort(v3.begin() , v3.end() ,Standard);
    answer = v3[0];
    return answer;
}

 

아래는 해결한 코드다.

 

#include<string>
#include<vector>
#include<algorithm>
 
using namespace std;
 
bool Standard(string A, string B)
{
    if (A + B > B + A) return true;
    return false;
}
 
string solution(vector<int> numbers)
{
    string answer = "";
    vector<string> array;
    for (int i = 0; i < numbers.size(); i++) array.push_back(to_string(numbers[i]));
    sort(array.begin(), array.end(), Standard);
    for (int i = 0; i < array.size(); i++)    answer = answer + array[i];
    
    if (answer[0] == '0') answer = "0";
    return answer;
}

 

간단하게 설명을 하자면 먼저 numbers 벡터에 있는 값을 string으로 변경해서 array 벡터에 넣어준다.

string 으로 변경하는 이유는 숫자들을 조합해서 문자열을 만들어야 풀이가 수월해진다.

6 , 10 ,2 가 값으로 주어진다면  정렬을 할때 standard 함수를 이용하는데

이때 6과 10을 문자열을 합치면 610 , 10과 6을 합치면 106 이 된다. 이때 610이 더 크므로 6 , 10 순서로 정렬된다.

이렇게 문자열을 쭉 정리하면 문자열을 합쳤을때 큰 수가 나오는 순서대로 정렬이 되고

각 원소들을 answer 문자열에 순서대로 합치면

가장 큰수를 만들어낼수있다.