[파이썬 알고리즘] 17장 가장 큰 수 (leetcode 179) - merge sort 이용

https://leetcode.com/problems/largest-number/

Largest Number - LeetCode

<문제>

Given a list of non-negative integers nums, arrange them such that they form the largest number.

Note: 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"

 

Example 3:

Input: nums = [1] Output: "1"

 

Example 4:

Input: nums = [10] Output: "10"

 

---

이 문제를 통해 얻어간 것

• bubble sort 구현 연습
• 문자간 비교하는 방법에 대한 생각! 💡
  • 7과 73을 비교하는 문제를, 773과 737을 비교하는 하는 문제로 바꾸어서 푸는 것

'''
61. 가장 큰 수
항목들을 조합하여 만들 수 있는 가장 큰 수를 출력하라.
https://leetcode.com/problems/largest-number/
'''
from typing import List

# 73과 7을 비교할 때
# "73"+"7"="737", "7"+"73"="773"을 비교하면 된다는 것!

# merge sort 이용한 풀이
class Solution:
    @staticmethod
    def compare(num1, num2):
        if str(num1) + str(num2) > str(num2) + str(num1):
            return True
        else:
            return False

    def merge(self, l1, l2):
        l1_index = 0
        l2_index = 0
        sorted_list = []
        while l1_index != len(l1) and l2_index != len(l2):
            if Solution.compare(l1[l1_index], l2[l2_index]):
                sorted_list.append(l1[l1_index])
                l1_index += 1
            else:
                sorted_list.append(l2[l2_index])
                l2_index += 1

        if l1_index != len(l1):
            sorted_list.extend(l1[l1_index:])
        else:
            sorted_list.extend(l2[l2_index:])
        return sorted_list

    def divide(self, nums: List[int]):
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2

        left = self.divide(nums[:mid])
        right = self.divide(nums[mid:])
        return self.merge(left, right)

    def largestNumber(self, nums: List[int]) -> str:
        ret = self.divide(nums)
        ret = ''.join(list(map(str, ret)))
        if int(ret) == 0:
            return "0"
        return ret