[프로그래머스 고득점 kit] 가장 큰 수 (C++)

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

프로그래머스

위 문제에 대한 풀이 입니다.

 

결국 각 입력값들은 하나의 "덩어리" 이다. 

ex) 402, 40 -> 402 // 40 은 각각 덩어리.

따라서 각 숫자간의 관계에서 어느 숫자가 앞에오는가? 만 정하면 된다.

 

ex1) 402, 432 

432,402 > 402,432

-> 432가 먼저와야한다.

 

ex2) 6, 543

6,543 >543,6

-> 6이 먼저와야한다.

 

ex3) 4,43

4,43 > 43,4

-> 4가 먼저와야한다.

 

ex4) 4, 49

49,4 > 4,49

-> 49가 먼저와야한다.

 

만약 위의 4가지 예제가 "모든" 상황에서 참인 명제라는 것을 이해했다면, 문제의 풀이는 끝났다.

'사전순' 으로 더 높은 순서를 가진 문자열이 앞에 오도록 구현하면 되는 것이다.

sort함수에서 compare함수를 a+b > b+a (a,b는 숫자 스트링)를 통해 구현했다. ( "12"+"3" <"3"+"12"  )

 

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

bool cmp(string a, string b){

        return a+b>b+a;// sort -> 결국 두 원소 중 뭐가 더 앞인가? 에 대한 것이다.
    //402,40  ->  40402  >40240  따라서 "무조건" 40이 앞에와야한다.
}

string solution(vector<int> numbers) {
    vector<string> v;
    for(int i=0; i<numbers.size();i++){
        v.push_back(to_string(numbers[i]));
    }
    string answer = "";
sort(v.begin(),v.end(),cmp);
    if(v[0][0]=='0')//크기순 정렬에서 맨앞이 0 -> 전부 0일시.
        return "0";// 정답이 "0000000" 이런식인 것 방지
    for(int i=0; i<v.size();i++){
        answer+=v[i];
    }
    return answer;
}

 

*주의

answer을 stoi로 int 로 만들고, 다시 to_string()으로 만드는 것으로, 숫자 string이 제대로된 숫자의 형태 ( ex: "03" 이 아닌 "3")를 띄게하려고 시도했지만 core dump 가 발생했다. 그 이유는, string 문자열은 "432423423424234.." 이런식으로 끝없이 높은 숫자를 가질 수 있지만, 이것을 int로 변환한다면, int는 물론이고, long long과 같은 타입도 버겁다. 그렇기에 string 값 자체를 가지고 제대로 된 숫자 타입으로 변환해야한다!