Python - functools.cmp_to_key (compare sort, 비교 정렬)

functools — Higher-order functions and operations on callable objects

cmp_to_key 함수는 파이썬의 old style 비교 함수다.

 

파이썬의 sort 함수를 사용하다 보면 람다식을 이용해서 중첩 리스트의 특정 요소를 기준으로 정렬한다던가 하는 방법을 종종 사용한다. 그런데 더 나아가서 정렬 기준을 커스텀하고 싶을 때가 있는데 이때 cmp_to_key 함수를 사용할 수 있다.

---

Prerequisite

Sort a list of lists with a custom compare function

커스텀 함수는 비교하고자 하는 값의 좌항이 더 작으면 -1, 크면 1, 같으면 0을 리턴 해주어야 한다. (오름차순 기준)

연습 문제

프로그래머스

위 문제는 주어진 숫자들을 이어 붙여서 가장 큰 수를 만드는 문제다. 

1. [3, 30], [987, 97] 같은 케이스는 일반적인 정렬만으로는 풀 수가 없다.
2. 그래서 결국 나이브하지만 모든 값을 일일이 비교하는 브루트 포스 풀이 방법을 생각하게 된다.
3. 그런데 주어지는 배열의 제한 길이가 최대 100,000 이므로 브루트 포스로 풀 수가 없다.
4. 그렇다면 Tim sort를 사용하는 python의 정렬 기준을 내 마음대로 커스텀 할 수는 없을까?

-> cmp_to_key 함수를 알게 되었다. 

 

 

풀이 및 사용 예시는 다음과 같다.

sorted 함수의 정렬 기준을  1 if int(x+y) < int(y+x) else -1  로 주어서 x+y, y+x 중에서 더 큰 값이 앞으로 오도록 정렬한다.

이때 네거티브와 포지티브의 값을 반대로 주어서 오름차순 정렬이 아닌 내림차순 정렬이 되게 했다.

from functools import cmp_to_key


def solution(numbers):
    nums = map(str, numbers)

    nums = sorted(
        nums, key=cmp_to_key(lambda x, y: 1 if int(x + y) < int(y + x) else -1)
    )

    return str(int("".join(nums)))