179. Largest Number - medium
문제
Given a list of non negative integers, arrange them such that they form the largest number.
제한사항
- The result may be very large, so you need to return a string instead of an integer.
입출력 예
1
2
3
4
5
6
7
Example 1:
Input: [10,2]
Output: "210"
Example 2:
Input: [3,30,34,5,9]
Output: "9534330"
풀이
- Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
bool comp(const string& a, const string& b){
// string인 a+b, b+a 중 큰것으로 정렬
// 예를 들어 a = "10", b = "2" 일때,
// a + b => "102"
// b + a => "210"
// 연산후, 이 둘을 비교하여 큰 값인 "210" 선택
auto str1 = a + b;
auto str2 = b + a;
return str1 > str2;
}
class Solution {
public:
string largestNumber(vector<int>& nums) {
string answer = "";
vector<string> numStr;
// 연산이 쉽도록 nums의 숫자를 모두 string으로 변환
for(auto& i : nums)
numStr.push_back(to_string(i));
// 사용자 비교함수대로 정렬
sort(numStr.begin(), numStr.end(), comp);
for(auto& i : numStr)
answer += i;
// "000"과 같은 경우를 체크하기 위해 문자열의 최대값을 구함
auto check = *max_element(answer.begin(), answer.end());
return check == '0' ? "0" : answer;
}
};