[알고리즘] Leetcode #179 가장 큰 수 (Python)

---

↓↓↓ 아래는 내 리트코드 & 깃허브 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

https://github.com/GodJiLee

GodJiLee - Overview

Leetcode #179 가장 큰 수

# 삽입 정렬
def to_swap(n1: int, n2: int) -> bool:
    return str(n1) + str(n2) < str(n2) + str(n1) # True면 위치 변경

# 삽입 정렬 수도 코드
i <- 1
while i < length(A)
    j <- i
    while j > 0 and A[j - 1] > A[j]
        swap A[j] and A[j - 1]
        j <- j - 1
    end while
    i <- i + 1
end while

이전에 구현해둔 연결리스트용 삽입 정렬과 달리 배열에 대한 풀이는 인덱스를 지정할 수 있음

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

# 전체 코드
class Solution:
    # 문제에 적합한 비교 함수
    @staticmethod # 
    def to_swap(n1: int, n2: int) -> bool:
        return str(n1) + str(n2) < str(n2) + str(n1)
    
    # 삽입 정렬 구현
    def largestNumber(self, nums) -> 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] # swap
                j -= 1
            i += 1
            
        return str(int(''.join(map(str, nums)))) # str을 nums로 변환

str(n1)을 먼저 붙인 것과 str(n2)를 먼저 붙인 것중 큰 것을 비교해 T/F를 반환하는 to_swap 함수를 구현해두고, largestNumber 함수에서 swap의 기준으로 사용한다. 이때, i = 1부터 시작해서 하나씩 늘려가면서 모든 자리를 비교해 최종 답을 얻도록 한다.

return하는 결과는 nums를 문자형으로 바꾼 후 하나로 join한 결과를 다시 정수형으로 만들었다가 다시 문자형으로 변형...

'00' 같은 경우 '0'으로 만들어주기 위함