[LeetCode 풀이/python] 179. Largest Number (medium)

문제 설명: 0 이상의 정수로 이루어진 배열 nums 가 주어졌을 때, 해당 배열을 구성하는 숫자들을 이용해서 만들 수 있는 가장 큰 숫자가 되도록 숫자들을 재구성하시오.

참고: 결과 값이 매우 클 수 있으므로, 정수가 아닌 문자열 형태로 리턴할 것.

 

(Given a list of non-negative integers nums, arrange them such that they form the largest number.

Note: The result may be very large, so you need to return a string instead of an integer.)

 

 

예시 1)

입력: nums = [10,2]  -->  출력: "210"

 

예시 2)

입력: nums = [3,30,34,5,9]  -->  출력: "9534330"

 

예시 3)

입력: nums = [1]  -->  출력: "1"

 

예시 4)

입력: nums = [10]  -->  출력: "10"

 

제한 조건:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9

 

------ * ------ * ------ * ------

 

[풀이 1안] (w/solution peeping)

• 접근법
  • 익숙한 문제였는데 알고보니 예전 프로그래머스 플랫폼에서 이래저래 풀어보다가 못 푼 채 남아있던 문제였다...ㅎㅎ
    • 그땐 일단 각 숫자를 문자열로 간주하고 정렬시킨 뒤, 해당 결과를 단순히 합치는 것(concat) 이 아니라 여러 경우를 나눠서 다시 정렬 순서를 조정하는 식으로 if 문을 짰다가 생각보다 엄청 복잡해져서 결국 GG 했는데...
  • 파이썬의 내장 정렬 함수(sorted) 에 대해 추가적인 parameter 조정을 통해 정렬 기준을 임의로 설정/변화시키는 방법이 가능하다는 것을 알게 됨!! ㅇㅁㅇ~
    • 내장 함수 sorted 의 key parameter 는 lambda 함수를 써서 인풋 튜플의 첫번째 인수를 기준으로 정렬한다거나... 그런 식의 사용은 익숙했는데, cmp_to_key() 라는 내장 함수 (functools 라이브러리 소속임) 를 이용해 보다 복잡한 정렬 기준 (인수 간 비교 기준!) 을 설정할 수 있었음
    • 배열에 포함되는 두 숫자를 앞뒤로 배치하여 만들어지는 두 정수 (x+y, y+x) 를 비교해서, (x+y) 가 (y+x) 보다 더 큰 경우 더 작은 값을 갖도록 (=선행하도록) 하는 함수를 새로운 비교 기준으로 설정~
    • 마지막 return 할 때 .lstrip('0') 은 최종적으로 구성된 문자열의 선단에 000.. 등으로 시작할 경우 이를 잘라내기 위함 & 그렇게 잘라냈을 때 아무것도 남지 않을 경우 (최종 결과가 0) '0' 을 리턴

 

• 코드 구현

def largestNumber(nums: List[int]) -> str:
    cmp = lambda x, y: -1 if x+y>y+x else (1 if x+y<y+x else 0)
    nums = sorted(map(str, nums), key=cmp_to_key(cmp))
    return ''.join(nums).lstrip('0') or '0'
    

 

• 결과
  • sorted 함수의 key 를 임의 변형시키면 함수의 시간 복잡도도 마냥 O(n log n) 이 아니라 달라질텐데, 내가 이해하기로는 해당 기준 적용시 O(1+2+...+(n-1)) = O((n-1)*n/2) = O(n^2) 가 될 듯..!
  • 입력 데이터 수가 아주 크게 주어지지 않아서 시간 / 공간 복잡도 모두 효율적으로 통과한 듯 ㅎㅎㅎ