[파이썬 알고리즘 인터뷰][정렬] 가장 큰 수

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

숫자 배열을 이어붙여 만들 수 있는 가장 큰 수 출력

 

책에서 구현된 코드

class Solution:
    # 문제에 적합한 비교 함수
    @staticmethod
    def to_swap(n1: int, n2: int) -> bool:
        return str(n1) + str(n2) < str(n2) + str(n1)

    # 삽입 정렬 구현
    def largestNumber(self, nums: List[int]) -> str:
        i = 1
        while i < len(nums):
            j = i
            while j > 0 and self.to_swap(nums[j - 1], nums[j]):
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
                j -= 1
            i += 1

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

 

기억해야할 기법

• 매우 중요한 문제(꼭 다시 볼것)
  
  • 정렬의 조건을 확인해서 lambda로 key에 표현할 수 있는지 확인
  • lambda로 표현이 어려울 경우, 정렬을 그냥 구현하자
  • 효율적인 정렬 구현이 부담스러울 경우, 버블소트로 구현하자
• '00'을 처리하기 위해 str -> int -> str

 

내가 구현한 코드

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # 머지 소트 구현
        def mergesort(A):
            def merge(left, right):
                result = []
                l = r = 0
                while l < len(left) or r < len(right):
                    if l == len(left):
                        result.append(right[r])
                        r += 1
                    elif r == len(right):
                        result.append(left[l])
                        l += 1
                    # 앞에 붙일 때 더 큰 값이 먼저
                    elif left[l] + right[r] > right[r] + left[l]:
                        result.append(left[l])
                        l += 1
                    else:
                        result.append(right[r])
                        r += 1
                return result
            if len(A) < 2:
                return A
            left = mergesort(A[:len(A)//2])
            right = mergesort(A[len(A)//2:])
            return merge(left, right)

        # str이므로 '0'이 2개일 경우 '00'을 출력
        if sum(nums) == 0:
            return '0'
        return ''.join(mergesort(list(map(str, nums))))

• 머지소트로 구현하다보니, 로직이 헷갈리기도 하고 구현 시간이 길어졌다
• 시간적 여유가 있는 문제가 아니라면, 매우 간단한 버블소트로 구현해도 될 것 같다