2레벨 : 가장 큰 수

현재 내 실력으론 해결법이 떠오르지 않아 인터넷의 솔루션을 참고하였다.

정수를 문자형으로 바꿔서, 처리해야지 까지는 생각하였지만, 모든케이스, 즉 각 숫자 더한 값에 따라 비교를 하나씩 전부다 함으로써, 시간복잡도가 n! 로 나와 시간초과 문제에서 막혀있었다. 

이를 효율적으로 하기 위해, 다른사람의 풀이를 본 결과, string vector를 하나 더 만들어서 기존 입력의 vector 인자들을 정렬 한 다음, (정렬시, 각 더한 결과가 더 큰쪽으로 오름차순 정렬되게) 이를 조건에 따라 먼저 나온 문자가 0이면 answer 에 0을 그 외의 경우, 해당 인자를 answer 값에 더해줌으로 원하는 정답을 리턴하는 경우로 해결을 하였다. 

 

아직 실력이 많이 부족함을 깨닫고 좀더 많은 문제를 풀어보고 사고력을 키워야 함을 느꼈다.

 

소스 코드는 아래와 같다. 

#include <string>
#include <vector>
#include <iostream>
#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> string_numbers;
    for(auto number:numbers){
        string_numbers.push_back(to_string(number));
    }
    sort(string_numbers.begin(), string_numbers.end(), compare);
    if(string_numbers[0] == "0"){
        return "0";
    }
    for(auto string_number : string_numbers)
        answer += string_number;
    return answer;
}