문제 개요
음이 아닌 정수로 이루어진 리스트가 주어졌을 때, 숫자들의 순서를 적절히 배치하여 만들 수 있는 가장 큰 수를 찾는 문제입니다. 예를 들어 배열이 [10, 2]라면 10을 먼저 두면 102가 되지만, 2를 먼저 두면 210이 되므로 정답은 210입니다.
해결 접근 방법
이 문제는 단순히 숫자 크기순으로 내림차순 정렬한다고 해결되지 않습니다. 예를 들어 [3, 30]에서 30이 더 큰 숫자이지만, 두 수를 이어 붙인 결과를 비교하면 330이 303보다 크기 때문에 3을 30보다 앞에 배치해야 합니다.
핵심은 두 숫자를 문자열로 연결했을 때 어느 순서가 더 큰 값을 만드는지 비교하는 것입니다. 두 숫자 x와 y에 대해 다음 규칙으로 정렬 순서를 결정합니다.
- x+y(두 문자열을 이어 붙인 결과)가 y+x보다 크면 x를 앞에 배치합니다.
- y+x가 x+y보다 크면 y를 앞에 배치합니다.
- 두 결과가 같으면 순서를 유지합니다.
이 비교 기준으로 정렬한 뒤 숫자들을 모두 이어 붙이면 가장 큰 수를 얻을 수 있습니다. 마지막으로 결과가 0으로만 구성된 경우(예: [0, 0])를 대비해 선행 0을 제거하고, 결과가 비어 있으면 0을 반환하도록 처리합니다.
구현 예제
아래는 파이썬의 functools.cmp_to_key를 사용해 사용자 정의 비교 함수를 sort에 적용한 구현 예입니다.
from functools import cmp_to_key
class Solution(object):
def largestNumber(self, nums):
for i in range(len(nums)):
nums[i] = str(nums[i])
nums.sort(key=cmp_to_key(lambda x,y:self.compare(x,y)))
return "".join(nums).lstrip("0") or "0"
def compare(self,x,y):
if x+y<y+x:
return 1
elif x+y == y+x:
return 0
else:
return -1
ob1 = Solution()
print(ob1.largestNumber([3,30,5,6,8]))입력
[3,30,5,6,8]
출력
"865330"
동작 원리 살펴보기
입력 [3, 30, 5, 6, 8]에 위 비교 기준을 적용해 정렬하면 8, 6, 5, 3, 30 순서가 됩니다. 특히 3과 30은 330이 303보다 크므로 3이 30보다 앞에 위치하며, 최종적으로 865330이라는 가장 큰 수가 완성됩니다.
복잡도 분석
- 시간 복잡도: O(n log n · k) — n은 숫자의 개수, k는 숫자의 평균 자릿수(문자열 연결 및 비교 비용 포함)
- 공간 복잡도: O(n · k) — 모든 숫자를 문자열로 변환하여 저장