[python/정렬] 31. 가장 큰 수(feat. functools.cmp_to_key 함수) ★

문제 출처

programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

- numbers의 길이는 1 이상 100,000 이하입니다.

- numbers의 원소는 0 이상 1,000 이하입니다.

- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

---

나의 코드(실패, 시간초과로 정확도 0)

from itertools import permutations

def solution(numbers):
    s = [str(x) for x in numbers]
    per = [''.join(x) for x in list(permutations(s, len(numbers)))]
    num = [int(x) for x in per]
    return str(max(num))

틀린 코드는 아닌 것 같지만 시간초과로 확인할 수 없었다ㅠ

 

다른 풀이

import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) 
    
def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

 

 

* cmp 매개 변수를 사용하여 정렬하는 방법(참고: docs.python.org/ko/3/howto/sorting.html)

sorted 함수로 데이터를 정렬할 때, cmp 매개 변수를 이용해서 사용자 지졍 비교 함수를 설정할 수 있다. 파이썬3 이상에서는 functools 모듈의 cmp_to_key, 그리고 사용자 정의 비교 함수를 이용해서 다음과 같이 적용할 수 있다.

def reverse_numeric(x, y):
	return y-x
sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))

그럼 결과값은 [5, 4, 3, 2, 1]를 반환한다.

 

이제 위의 문제에서 첫 번째 예시 [6, 10, 2]를 입력했다고 가정해보자.

사용자 정의 비교 함수 comparator를 통해서 각각의 인자를 비교하게 될 것이다.

 

1) 6을 기준을 10과 비교하게 되면 610(6+10) > 106(10+6)이므로 10보다 6의 우선순위가 높으므로 10보다 6이 먼저 출력된다.

   (옵션이 없다면 10이 먼저 출력될 것이지만, reverse=True라는 옵션이 있기 때문에 내림차순 정렬이 되기 때문)

2) 같은 방법으로 6을 기준으로 2와 비교하게 되면 62 > 26이므로 2보다 6이 먼저 출력된다.

3) 10을 기준으로 2와 비교하게 된다면 210 > 102이므로 10보다 2가 먼저 출력한다.

 

이 세가지를 종합하면 [6, 2, 10]로 정렬될 것이고, 결론적으로 solution함수를 통해서 '6210'가 반환된다.