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

https://programmers.co.kr/learn/courses/30/lessons/42746

처음 시도 (시간 초과)

int 벡터를 순열로 돌리고, string으로 만들어주면서 string벡터에 push하고... 마지막에 string벡터 정렬 후 제일 큰 숫자 값 리턴하는 형식인데 시간초과였다... 🙂

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

using namespace std;

string solution(vector<int> numbers) {
    string answer = "";
    int maxVal=-1;    
    sort(numbers.begin(),numbers.end());
    
    vector<string> res;
    do{
        string str="";
        for(auto n:numbers) str+=to_string(n);
        res.push_back(str);
    }while(next_permutation(numbers.begin(),numbers.end()));
    
    sort(res.begin(),res.end());
    answer=res[res.size()-1];
    return answer;
}

풀이

• int 벡터를 string으로 옮기고 정렬 한 번만 하면 끝나는 문제였다.

• 그 정렬 기준은 string a, b가 있을 때 a+b, b+a 중 큰 순으로 내림차순 하는 것이다.
  예를 들면 "6","10"이 있을 때 "6"+"10"="610" / "10"+"6"="106" 이므로 더 큰 숫자가 나오는 순인 "6","10"으로 정렬되어야 한다.

• 따라서 sort함수 기준을 내가 만들어주면 된다

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

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(const string &a, const string &b){
        return a+b>b+a;     
}
string solution(vector<int> numbers) {
    string answer = "";
    //int->string
    vector<string> array;
    for(auto num:numbers) array.push_back(to_string(num));
    
    //문자 2개를 합쳤을 때, 더 큰 게 앞에 오도록!
    sort(array.begin(),array.end(),compare);
    
    if(array[0]=="0") return "0"; //제일 큰 수가 0일 때
    
    //답 만들어줌
    for(auto s:array) answer+=s;
    
    return answer;
}