[프로그래머스 lv2] 가장 큰 수 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

주어진 수들을 연결하여 만들 수 있는 가장 큰 수를 문자열로 리턴하는 문제이다.

numbers를 올바른 방법으로 정렬 할 수 있다면, 정렬 된 수들을 모두 연결하여 리턴하면 된다.

 

그런데, 정렬 기준을 세우는게 생각보다 까다롭다.

각 자릿수를 비교하다가 큰 수가 더 앞에 나와야 하는 건 알겠는데,

3과 30을 보면, 330이 303보다 크므로, 무조건 크다고 해서 앞에 오는 건 아니다.

 

두 수를 비교할 때 무엇이 앞에 와야하는지 조금 더 간단하게 판단할 수는 없을까? 

두 문자열(수) a, b가 있을 때, 두 수를 합친 결과는 a+b나 b+a 이다.

만약 a+b >  b+a 라면 a가 앞에 오면 되고, a+b < b+a 라면 b가 앞에 오면 된다.

 

정렬 기준을 cmp 함수로 구현하여 sort()의 매개변수로 넘기긴다.

(bool cmp(string a, string b) 는 a가 앞에 와야 할 때 true를 반환한다.)

 

최종 문자열이 "00000.." 일 때 "0"을 반환하도록 예외처리하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

bool cmp(string a, string b) {
    
    if (a+b > b+a) return true;
    return false;
}

string solution(vector<int> numbers) {
    
    vector<string> v;
    for (auto x : numbers) v.push_back(to_string(x));
    sort(v.begin(), v.end(), cmp);
    
    string s = "";
    for (auto x : v) s += x;
    
    if (s[0] == '0') return "0";
    return s;
}