LeetCode [179]: Largest Number

📌 LeetCode [179]: Largest Number

🔗 문제 링크

---

문제 설명 📄

주어진 비음수 정수 배열 nums를 사용해 숫자를 조합하여 가장 큰 숫자를 생성하세요.
결과는 문자열로 반환하며, 숫자가 0만 포함된 경우에는 "0"을 반환합니다.

---

문제 해결 접근 🧩

1. 숫자를 조합하여 가장 큰 수를 만들기 위해 문자열로 변환.
2. 두 문자열 x와 y를 비교할 때, x+y와 y+x를 비교하여 정렬 순서를 결정.
3. 정렬된 숫자를 이어붙여 결과를 반환.
4. 첫 번째 숫자가 "0"인 경우 전체 숫자가 0이므로 "0"을 반환.

---

Solution 💻

원래 코드

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def custom_sort(x, y):
            if x + y > y + x:
                return -1 
            elif x + y < y + x:
                return 1   
            else:
                return 0 
        nums = list(map(str, nums))
        sorted_nums = sorted(nums, key=cmp_to_key(custom_sort))
        if sorted_nums[0] == '0': 
            return "0"
        return "".join(sorted_nums)

시간 복잡도 ⏲️

• 정렬 시간 복잡도: O(n log n)
  (n)은 배열 nums의 길이.
• 비교 함수 호출 비용: 각 비교에서 O(1) 문자열 비교 수행.
• 총 시간 복잡도: O(n log n).

공간 복잡도 🗄️

• 문자열로 변환된 숫자 배열: O(n).
• 정렬 결과 저장 공간: O(n).
• 총 공간 복잡도: O(n).