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

[구현 환경]

• C++

[문제 설명]

• 정수를 이어 붙여 만들 수 있는 가장 큰 수를 return
• 0 혹은 양의 정수가 담긴 배열 numbers가 주어지며, 순서를 재배치해 만들 수 있는 가장 큰 숫자를 문자열로 바꿔 return
• 제한사항
  • numbers의 길이는 1 이상 100,000 이하
  • number의 원소는 0 이상 1,000 이하

[함수 원형]

string solution(vector<int> numbers) {
	string answer;
    
	return answer;
}

[풀이]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(vector<int> numbers) {
    
    if (numbers.size() < 0 || numbers.size() > 100'000) return "0";
    
    string answer = "";

    auto _sort = [](int a, int b)
    {
        auto aStr = to_string(a);
        auto bStr = to_string(b);

        return aStr + bStr > bStr + aStr;
    };

    sort(numbers.begin(), numbers.end(),_sort);

    for (auto n : numbers)
    {
        answer += to_string(n);
    }

    if (answer[0] == '0') return "0";
    return answer;
}

• 비교할 두 숫자를 앞 뒤로 더해 내림차순으로 정렬하는 람다함수 _sort 구현
• 이후 순서대로 문자열에 붙여가면서 answer를 생성
• answer의 첫번째 문자가 '0'일때는 answer가 모두 0으로 이루어져있으므로 "0"을 return

[시행착오]

string solution(vector<int> numbers) {
    string answer = "0";

    sort(numbers.begin(), numbers.end());
    
    do
    {        
        string temp="";
        for(int i=0;i<numbers.size();++i)
        {
            temp += to_string(numbers.at(i));
        }
        
        if (answer.compare(temp) < 0) answer = temp;
        
    }while(next_permutation(numbers.begin(), numbers.end()));

    return answer;
}

• 최초로 구현한 코드 => 조합식 만들어서 돌아다니면서 최대값 찾기
  • 거의 모든 케이스에서 timeout 발생
  • 정렬로 풀어야겠다고 생각