difficulty: Medium
Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
음수가 아닌 정수들의 배열이 주어지면, 해당 정수들을 배치해 가장 큰 수를 구성하고 반환해라.
Since the result may be very large, so you need to return a string instead of an integer.
결과가 매우 클 수 있기 때문에, 정수형 대신 문자열 타입으로 반환해라.
Example 1:
Input: nums = [10,2]
Output: "210"
Example 2:
Input: nums = [3,30,34,5,9]
Output: "9534330"
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 10^9
단순히 생각하기로는, 각 자리별로 가장 큰 수를 앞으로 배치하면 될 것 같다고 생각했습니다.
예를 들어, [9, 8, 7] 이 있다면 9 8 7 이렇게 배치하는 식입니다.
[99, 98, 97] 이렇게 앞 자리가 같다면, 뒷 자리를 비교해 99 98 97 이런 식으로 배치해주면 될 것 같았습니다.
이런 식으로 Greedy 하게 풀어도 최적의 결과를 보장할 수 있기 때문에 한 번 구현해보았습니다.
class Solution {
public:
static string concatenateInts(const std::vector<int> &nums) {
std::stringstream ss;
for (int num : nums) {
ss << num;
}
return ss.str();
}
static bool compare(int num1, int num2) {
string combination1 = to_string(num1) + to_string(num2);
string combination2 = to_string(num2) + to_string(num1);
return combination1 > combination2;
}
static bool checkAllZero(vector<int>& nums) {
bool flag = true;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != 0) {
flag = false;
break;
}
}
return flag;
}
string largestNumber(vector<int>& nums) {
if (checkAllZero(nums)) return "0";
sort(nums.begin(), nums.end(), compare);
return concatenateInts(nums);
}
};코드에 대해 설명드리겠습니다.
비교 함수에서 두 문자열을 합쳐 사전순으로 앞서는 순서대로 정렬합니다.
이 때, 사전순이라는 것은 ascii code 순서입니다. 0은 48, 9는 57의 값을 가지므로 "0" < "9" 가 됩니다.
만약 문자열이라면 두 문자열의 각 문자를 차례대로 비교합니다.
예를 들어 "999" "989" 이라면
첫 번째 문자 비교 "9" == "9"
두 번째 문자 비교 "9" > "8" 문자열 비교 종료
세 번째 문자 비교는 이루어지지 않는다.
정렬한 뒤 stringstream을 이용해 이어붙여 문자열을 만들고 그 결과를 반환합니다.
처음에 고려해주지 못한 점은 [0,0] 등의 vector가 들어왔을 때, "0"으로 표기해주었어야 했는데 "00"으로 표기되었다는 점입니다.
해당 조건을 막아주기 위해 모든 원소가 0인 경우만 찾아 return "0"을 반환하는 부분을 추가해주었습니다.
runtime은 제출할 때마다 제각각이라서, '내 접근 방식이 일반적이거나 적절하구나' 라고 생각하기로 했습니다.
주로 python을 이용해 알고리즘 문제를 풀다가, C++를 이용하니 문법이 익숙하지는 않지만 재미있는 것 같습니다. :)
학습하고 있는 언어가 있거나 배워보고 싶은 언어가 있다면, 그리고 알고리즘 문제를 푸는 것을 즐기신다면 문법을 익히는데도 도움이 될 것 같네요.
혹시 궁금한 점이 있으시거나 잘못된 부분, 고칠 부분이 있으면 언제든지 의견 부탁드리겠습니다. 긴 글 읽어주셔서 감사합니다!
