LeetCode) Largest Number

주어진 배열에 있는 숫자를 문자열로 붙여서 가장 큰 수를 만들어야 하는 문제다.

 

 

정렬방식 중 비교구문만 바꿔주면 된다. merge sort코드를 구글링해와서 비교구문만 바꿔주었다.

3 과 30 을 비교하는 방법:  330, 303 비교 

class Solution():
    def largestNumber(self, nums: List[int]) -> str:
        def merge_sort(arr):
            if len(arr) < 2:
                return arr

            mid = len(arr) // 2
            low_arr = merge_sort(arr[:mid])
            high_arr = merge_sort(arr[mid:])

            merged_arr = []
            l = h = 0
            while l < len(low_arr) and h < len(high_arr):
                if int(str(low_arr[l]) + str(high_arr[h])) >= int(str(high_arr[h]) + str(low_arr[l])):
                    merged_arr.append(low_arr[l])
                    l += 1
                else:
                    merged_arr.append(high_arr[h])
                    h += 1
            merged_arr += low_arr[l:]
            merged_arr += high_arr[h:]
            return merged_arr

        return str(int("".join(map(str,merge_sort(nums)))))