[리트코드] 179. 가장 큰 수 (Python)

LeetCode - The World's Leading Online Programming Learning Platform

문제

음이 아닌 정수 리스트 nums이 주어지면 가장 큰 수를 구성하도록 정렬하세요.

과정

• 리스트 차례대로 두 개씩 원소를 조합하고 그 수를 비교한 다음
• 더 큰 조합이 나오도록 원소를 오른쪽으로 옮기는 방법을 사용해서
• 리스트를 하나로 합쳤을 때 가장 큰 수가 나오도록 정렬한다.

 

입력

[10,2]

출력

"210"

 

풀이

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        for i in range(1, len(nums)):
            for j in range(i, 0, -1):
                if self.compare(nums[j-1], nums[j]):
                    nums[j-1], nums[j] = nums[j], nums[j-1]
        
        return str(int(''.join(map(str, nums))))

    def compare(self, n1, n2):
        return str(n1) + str(n2) < str(n2) + str(n1)

 

한 줄 씩 해석해보기

def compare(self, n1, n2):
    return str(n1) + str(n2) < str(n2) + str(n1)

• 비교를 하기위한 compare함수를 만들어준다. n1과 n2를 받는다
• 문자열로 변환한 n1 + n2 보다 n2 + n1 이 더 크다면 True를 반환한다. 

for i in range(1, len(nums)):
    for j in range(i, 0, -1):
        if self.compare(nums[j-1], nums[j]):
            nums[j-1], nums[j] = nums[j], nums[j-1]       
return str(int(''.join(map(str, nums))))

• 배열의 1번째 인덱스부터 탐색한다.
• 탐색하는 위치의 이전 값들을 비교한다.
• 만약 compare함수에 배열의 현재 탐색값과 이전 값을 넣었을때 True라면
• 두개의 위치를 바꾸어준다. 
• 반복 후 출력한다.

 

간단한 풀이

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums.sort(key=lambda x: str(x)*10, reverse=True)
        return str(int("".join([str(n) for n in nums])))

• 9자리 숫자까지 입력 받을 수 있으므로 lambda를 이용해 문자열로 변환하여 10번 정렬해준다.