[LeetCode] 179. Largest Number(파이썬/python) (with. cmp_to_key)

🎈문제

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

🎁어떤 알고리즘?

정렬

1. 처음엔 permutation으로 가능한 모든 조합을 찾아서 풀려 했는데 확실히 순열은 개수가 10만 넘어가도 시간초과가 나기 쉽다.

2. cmp_to_key를 활용한 풀이

 

cmp_to_key()에 대한 설명

from functools import cmp_to_key

def compare(a,b):
	if a > b:
		return 1
	elif a == b:
		return 0
	elif a < b:
		return -1

lst = [1,3,2]

lst = sorted(lst, key=cmp_to_key(compare))
print(lst)

# 결과 : [1,2,3]

• cmp_to_key는 -1,0,1을 파라미터로 받는다.(따라서 compare는 -1,0,1을 반환해야한다.)
  • 1 : 첫번째 값(a)가 두번째 값(b) 보다 큼을 의미한다. 즉, 정렬할 때, a가 b보다 앞에 와야할 때 1을 return 한다.
  • 0 : 첫번째 값(a)가 두번째 값(b)와 같음을 의미한다. 즉, 정렬할 때, a와 b가 같은 위치에 그대로 있어야 할 때 0을 return한다.
  • -1 : 첫번째 값(a)가 두번째 값(b)보다 작음을 의미한다. 즉, 정렬할 때, a가 b보다 뒤에 와야할 때 -1을 return 한다.

 

• 결론 : a,b 비교할 때 순서 바꿔야되면 1, 순서 안바꿔도 되면 -1 return
  • a < b 일 때, 순서를 바꾸고 싶다면 return 1
    • 3 < 1 일 때, 순서를 바꾼다면 정렬은 [3,2,1] 순서가 됨
  • a < b 일 때, 순서를 바꾸고 싶지 않다면 return -1
    • 3 < 1 일 때, 순서를 바꾸지 않으면 정렬은 [1,2,3] 순서가 됨

 

 

💻 cmp_to_key()를 활용한 정답 코드

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def compare(a,b):
            if a+b < b+a:
                return 1
            else:
                return -1
        
        nums = list(map(str,nums))
        nums = sorted(nums, key=cmp_to_key(compare))
        return str(int(''.join(nums)))

 

 

❌permutation을 활용한 시간초과 코드

from itertools import permutations
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        max_num = 0
        for lst in permutations(map(str,nums),len(nums)):
            num = ''.join(lst)
            max_num = max(int(num),max_num)
        
        return str(max_num)