가장 큰 수

문제

풀이

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

using namespace std;

bool compare(pair<int,int> a, pair<int,int> b)
{
    return a.first > b.first;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<pair<int,int>> v;
    for(int i=0;i<numbers.size();i++)
    {
        if(numbers[i] == 0) v.push_back(make_pair(0,i));
        else if(numbers[i] == 1000) v.push_back(make_pair(1000,i));
        else if(numbers[i] < 1000 && numbers[i] > 99){
            v.push_back(make_pair(numbers[i]*1000+numbers[i],i));
        }
        else if(numbers[i] < 100 && numbers[i] >9){
            v.push_back(make_pair(numbers[i]*10000+numbers[i]*100+numbers[i],i));
        }
        else{
            v.push_back(make_pair((numbers[i]*100000)+(numbers[i]*10000)+(numbers[i]*1000)
                                  +(numbers[i]*100)+(numbers[i]*10)+numbers[i],i));
        }
    }
    sort(v.begin(),v.end(),compare);
    
    for(int i=0;i<v.size();i++)
    {
        string s = to_string(numbers[v[i].second]);
        answer += s;
    }
    
    if(v[0].first == 0)
    {
        answer = "0";
    }
    
    return answer;
}

// 문자열이 있으면 그 문자열의 첫번째 부분들을 비교하여 sort를 한다.

// 그리고 모든값에 10을 곱하고 기존값에 두번째자릿수를 더하여 sort한다.

// 그리고 모든값에 10을 곱하고 기존 값에 세번째 자릿수를 더하여 sort한다.

// 1과 10과 100의 구분을 어케할 것인가, 100이 뒤로가는 것이 가장 바람직함. pair로 length를 기억한다. 
// 값이 같다면 뒤의 length가 짧은 것이 먼저인것으로
// 근데 위와 같이 한다면 924 와 92가 있다하면? 92924, 92492
// length별로 따로 모아서 sort를 한다. 

// 99와, 9를 더해주는 방식으로 하자.

// 3과 34의 경우 34가 먼저와야 한다. 3은 33까지는 커버가능

// 3과 334 3343, 3334

// 3의경우는 3333으로 해야겟네, 그리고 10의 자리의 경우를 보면 303, 303 = 30 330, 303 30 

// 30 303 , 30 330, 30 303

// 12 , 1212 짝수일때는 문제가 생기지X

// 홀수일떄가 문제인거지, 303의 경우 303
// 그러면 짝수로 만들어줘 홀수도 그런 수는 무엇인가? 6자릿수로 만들어

// 9786 97869 9786 99786, 97869 9786

맞왜틀을 1시간 정도 외치다가, 포기를 하고 정답을 봤다.
너무 사소한데에서 실수를 했다. 전체가 0인 경우를 확인을 하지 않은 것이었다.
이경우 answer의 결과값이 000000 이 될테니 이것은 문제가 발생할것이다.
이를 0으로 해줬어야 했다..

어떻게하면 정렬 시, 우선순위에 맞게끔 정렬이 될까에 대해서 생각을 많이 했다.
그렇게 해서 나온 결론이 숫자에 1000, 10000, 100000 를 곱하여 여섯자리로 만들고, 0으로 채워진 부분을 앞에 숫자가 있는 부분과 같은 패턴으로 연속하게 나오면 된다고 생각을 했다. 그래서 여섯자리를 고른것이다. 예를들어 자리수가 하나인 경우에는 111111 으로, 두개인 경우에는 121212, 세개인 경우에는 303303 이런식이다. 이렇게 만들어 준 이후 sort를 했다. 이 때 pair를 통해 index도 기억을 해주었다.

더 좋은 풀이 방법은 4자리의 string으로 만들어서 비교를 string값을 비교해주는 방법이었다.