# 람다 함수로 맨 앞글자 기준으로 sorting -큰게 맨 앞으로 오게
# 만약 앞글자가 같다면, 두번째 글자 기준에서 큰거 , 두번째 글자가 같다면,
def solution(numbers):
l = sorted(list(map(str,numbers)),reverse =True,key=lambda x: x * 3)
a = "".join(l)
if a[0] =='0':
return '0'
else:
return a(1) map(str, numbers)
- 원소 개수: n
- 각 숫자를 문자열로 변환: O(1)
- 전체: O(n)
(2) key=lambda x: x * 3
- sorted는 각 원소마다 key를 한 번만 계산
- 문자열 길이 최대: 상수 (≤ 4자리 → x*3도 상수 길이)
- 전체 key 계산 비용: O(n)
(3) sorted()
- 파이썬 sorted는 Timsort
- 평균/최악 시간 복잡도: O(n log n)
- 비교는 key 값 기준으로 수행됨
O(n) + O(n) + O(n log n)
= O(n log n)
Comparator를 쓰든, key를 쓰든
빅오(Big-O) 시간 복잡도는 같다.
하지만 “상수 시간”과 실제 성능은 다르다.
방식정렬 복잡도비교 호출 수실무/코테 추천
| key= 방식 | O(n log n) | n번 |
| Comparator | O(n log n) | n log n번 |
👉 빅오는 같지만 실제 실행 시간은 다름
key 방식
numbers.sort(key=lambda x: x*3, reverse=True)
동작 방식
- 각 원소에 대해 key를 딱 한 번만 계산
- 정렬은 key 값끼리만 비교
key 계산 횟수 = n
비교 횟수 = n log n
Comparator 방식
from functools import cmp_to_key
def cmp(a, b):
return (b+a > a+b) - (b+a < a+b)
numbers.sort(key=cmp_to_key(cmp))
동작 방식
- 정렬 중 비교할 때마다 cmp(a, b) 호출
- cmp 내부에서 문자열 덧붙이기 + 비교 매번 수행
cmp 호출 횟수 ≈ n log n
각 cmp 호출 비용 > O(1)
“가장 큰 수” 기준으로 비교하면
Comparator는 내부에서 매번 이걸 함
a + b
b + a
문자열 생성 + 비교
이게 정렬 내내 반복
key 방식은?
x * 3
한 번만 생성
이후엔 그냥 문자열 비교
시간 복잡도 정리 (정확하게)
key 방식
key 계산: O(n)
정렬: O(n log n)
총합: O(n log n)
Comparator 방식
비교: O(n log n) × 비교 비용
총합: O(n log n)
빅오는 같지만 Comparator는 비교 비용이 훨씬 큼
코테에서 Comparator가 불리한 이유
- 시간 초과 위험
- 코드 길어짐
- 실수 가능성 증가
- 파이썬에서는 cmp_to_key 자체가 오버헤드
그래서 파이썬 문제 해설 대부분
key=lambda x: x*3
이 패턴을 씀
그럼 Comparator는 언제 쓰나?
key로 표현 불가능할 때
- 복합 규칙
- 동적 비교
- 정렬 기준이 상황에 따라 바뀔 때
Comparator를 사용하더라도 정렬 알고리즘의 시간 복잡도는 O(n log n)으로 동일하지만,
비교 함수가 정렬 과정에서 반복적으로 호출되기 때문에 실제 실행 시간은 key 방식보다 느릴 수 있다.