가장 큰 수

첫 시도

테스트 케이스는 모두 통과해서 틀린 이유를 찾는데 너무 오래 걸렸다. 

처음 생각한 알고리즘은 숫자를 문자열로 변환한 후 첫째자리의 수부터 순차적으로 비교하는 것이였는데

이 경우 [18, 27] 일때 "1827"로 잘못 정렬되는 것을 확인할 수 있었다.

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

using namespace std;

bool cmp(int a, int b){
    
    string s1=to_string(a);
    string s2=to_string(b);
    
    int minlen=min(s1.length(), s2.length());
    int i=0;
    while(minlen--){

        if(s1[s1.length()-i-1]==s2[s2.length()-i-1]) {
            i++;
            continue;
        }
        else break;
    }
    return s1[s1.length()-i-1]>s2[s2.length()-i-1];

}

string solution(vector<int> numbers) {
    
    string answer = "";
    sort(numbers.begin(),numbers.end(),cmp);
    
    for(int i=0; i<numbers.size(); i++){
        answer+=to_string(numbers[i]);    
    }
    
    return answer;
}

두번째 시도

구글링과 친구에게 질문한 후 방법을 알아냈다. 정말로 구글링 안하고 싶은데 도대체 이런 풀이방법은 어떻게 알아내는 것인가...

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

using namespace std;

bool cmp(int a, int b){
    
    string s1=to_string(a);
    string s2=to_string(b);
    
    for(int i=0; i<4; i++){
        s1+=s1;
        s2+=s2;
    }
    
    string rs1="",rs2="";
    
    for(int i=0; i<4; i++){
        rs1+=s1[i];
        rs2+=s2[i];
    }

    return rs1>rs2;
}

string solution(vector<int> numbers) {
    
    string answer = "";
    sort(numbers.begin(),numbers.end(),cmp);
    
    for(int i=0; i<numbers.size(); i++){
        answer+=to_string(numbers[i]);    
    }
    //이부분때문에 1시간 넘게 고민했다. "0000"의 경우 "0"으로 바꿔주는 부분
    if(answer[0]=='0') answer=to_string(stoi(answer));    
    return answer;
}

핵심 아이디어는 숫자를 문자로 변환후 "a"=>"aaaa"이런식으로 반복된 문자열로 확장시킨후 사전순으로 비교하는 것이다.