Leetcode 179. Largest Number - Python

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다

Leetcode 179 문제 보기

 

문제 이해하기

주어진 nums 리스트에는 양의 정수들이 있다.

이들을 조합하여 만들 수 있는 가장 큰 수를 구하라.

 

예를 들어 nums = [3,30,34,5,9] 일 경우, 정답은 "9534330" 이다.

 

아이디어 구상

주어진 예시에서 알 수 있듯이, 단순히 큰 수를 앞으로 놓는다고 해결되지 않는다.

각각의 digit이 가능한 큰 숫자가 오도록 나열해야 정답을 구할 수 있다.

 

때문에 nums 안에 있는 각각의 숫자를 String으로 만들고,

두 개의 원소 n1, n2를 순서를 바꿔 결합하여 대소 관계를 비교, 큰 수가 앞서도록 정렬하면 되겠다.

By Mesotes

 

그렇다면 이제 어떻게 이 과정을 코드로 옮길지가 고민이다.

단순히 생각해보면, nums 리스트 내 모든 원소들에 대해 두 개씩 서로 비교하며,

더 큰 수가 앞에 오도록 서로 위치를 바꿔가는 과정을 반복하면 될 것이다.

즉, 일종의 Bubble sort 방식이다.

또한 두 개의 포인터와 스왑을 이용하여 Insertion sort를 할 수도 있겠다.

 

그러나 파이썬의 훌륭한 Tim sort 내장 알고리즘을 사용하여 이를 O(nlogn)에 해결해보자.

파이썬의 cmp_to_key를 사용하면 다소 복잡한 정렬 기준이라도 커스터마이징할 수 있다.

 

풀이

우선 각각의 원소를 String으로 변환하자.

str_nums = [str(i) for i in nums]

 

cmp_to_key의 사용법은 다음과 같다.

여기서 comparator는 정렬 기준이 되는 함수로, 개발자가 자유롭게 정의하면 된다.

res = ''.join(sorted(str_nums, key=cmp_to_key(comparator)))

 

comparator는 다음과 같다.

두 String 원소를 순서를 바꿔 결합하고 이 둘을 대소 비교한다.

 

return 값은 양수, 음수, 혹은 0이 가능하다.

0의 경우 순서 그대로, 양수라면 나중에 들어온 원소가 앞으로, 음수라면 먼저 온 원소가 앞으로 정렬된다.

def comparator(n1: str, n2: str) -> int:
    if n1 + n2 > n2 + n1:
        return -1
    else:
        return 1

 

이후 마지막 return 시 정답의 제일 첫번째 숫자가 0일 경우를 처리하기 위해 다음과 같이 처리해주자.

return str(int(res))

 

전체 코드는 다음과 같다.

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        str_nums = [str(i) for i in nums]
        
        def comparator(n1: str, n2: str) -> int:
            if n1 + n2 > n2 + n1:
                return -1
            else:
                return 1
        
        res = ''.join(sorted(str_nums, key=cmp_to_key(comparator)))
        
        return str(int(res))

 

---

Leetcode 179. Largest Number

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

 

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다