Published:
Updated:


SolutionPermalink

from typing import List


class Solution:
    # μ‚½μž… μ •λ ¬ 문제
    # κ°€μž₯ 큰 수λ₯Ό λ§Œλ“€μ–΄μ„œ λ¬Έμžμ—΄λ‘œ λ°˜ν™˜
    def largestNumber(self, nums: List[int]) -> str:
        # μ•žμžλ¦¬κ°€ κ°€μž₯ 큰 수둜 μ •λ ¬, κ·Έ λ‹€μŒμ—λŠ” κ·Έ λ‹€μŒ μˆ«μžλ“€λ‘œ μ •λ ¬
        # μ‚½μž… 정렬도 μŠ€μ™‘ μ΄μš©ν•˜λ©΄ 될 λ“―?
        for i in range(len(nums)):
            # Discusstion:
            # The solution of the problem rests on observing that if AB > BA.
            # Then we have ACB > BCA for any C.
            for j in range(i, 0, -1):
                if int(str(nums[j - 1]) + str(nums[j])) < int(str(nums[j]) + str(nums[j - 1])):
                    nums[j - 1], nums[j] = nums[j], nums[j - 1]
                    continue

                break

        return str(int(''.join(list(map(str, nums)))))


ReferencePermalink

Leave a comment