Programmers / Level 2 / 가장 큰 수 / C++

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고,
이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를
문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

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

using namespace std;

bool compare(string s1, string s2) {
    // s1+s2가 s2+s1보다 크도록 정렬
    return s1+s2 > s2+s1;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> s;
    
    for(int n : numbers) {
        s.push_back(to_string(n));
    }
    
    sort(s.begin(), s.end(), compare);
    
    for(string str : s) {
        answer += str;
    }
    
    if(s[0] == "0") return "0";
    
    return answer;
}

---

숫자가 길어질 경우 문자열로 바꿔줘야 하기 때문에 주어진 numbers벡터를 string으로 치환해 새로 옮겨주었다.

그리고나서 sort()함수에 세 번째 인자로 들어갈 사용자 정의 함수를 만들어 주었다.

 

compare 함수를 보면 문자열 두개를 인자로 받는데,

함수의 내용을 예를 들어 설명하자면 이렇다.

 

문자열은 '+' 연산자를 통해서 이어붙일수가 있다.

예를들어 "123" + "456"은 "578"이 되는것이 아니라 그대로 이어붙여서 "123456"이 된다.

sort의 맨마지막 인수로 함수를 적게되어주면 맨앞부터 차례대로 비교를 하게된다.

 

따라서 예를들어 첫번째가 "12"이고 두번째가 "34"면,

compare함수의 인자인 s1과 s2에 각각 "12"와 "34"가 전해지고,

"1234"가 더크냐, "3412"가 더크냐를 비교해서 bool값을 리턴해주는 것이다.

 

비교를 해서 true를 가지는 값으로 return이 된다.

 

마지막의 if문은 맨앞이 "0"이면 그냥 제일 작은 수 이므로, "0"을 return 해주면된다.