[프로그래머스, python3] 가장 큰 수(sorted, cmp_to_key )

 

[프로그래머스, python3] 가장 큰 수(sorted, cmp_to_key )
난이도	Level 2
분류	정렬
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 합니다.

입출력 예

numbersreturn

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

 

소스코드

cmp_to_key

import functools
 
#  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0
def comparator(a,b):
    t1, t2 = a+b, b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) 
 
def solution(numbers):
    n = list(map(str, numbers))
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

 

cmp_to_key + lambda

import functools
 
def solution(numbers):
    n = list(map(str, numbers))
    n = sorted(n, key=functools.cmp_to_key(lambda x,y: int(x+y)-int(y+x)),reverse=True)
    answer = str(int(''.join(n)))
    return answer

 

• cmp_to_key와 lambda를 같이 사용한 구조
• 전체적으로 처리시간이 cmp_to_key만 사용했을 때 보다 줄어들음

 

lambda

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

• 각 원소를 3개씩 연속한 값을 만들고, 그 값을 기준으로 내림차순 정렬을 진행한다.
•  x 3만 하는 이유는 입력 numbers의 값이 0 이상 1000 이하이기 때문이다. 
• 전체적으로 처리시간이 cmp_to_key만 사용했을 때와 cmp_to_key + lambda를 사용했을 때보다 줄어들음

 

소스코드 분석

cmp_to_key

import functools
 
def comparator(a,b):
    t1, t2 = a+b, b+a
    print(f"comparator: {a},{b} -> {t1},{t2} -> {(int(t1) > int(t2)) - (int(t1) < int(t2))}")
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0
 
def solution(numbers):
    n = list(map(str, numbers))
    print(f'input -> {n}')
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    print(f'n -> {n}')
    answer = str(int(''.join(n)))
    return answer
 
if __name__ == "__main__":
    print('-' * 40)
    numbers = [[6, 10, 2], [3, 30, 34, 5, 9], [0,0,0,0,0,0]]
    correct_answer = ["6210", "9534330", "0"]
 
    for t in range(len(numbers)):
        answer = solution(numbers[t])
        print('answer :' + answer, '/ correct_answer :' + correct_answer[t])
        if correct_answer[t] == answer:
            print(f'테스트 {t}를 통과하였습니다.')
        else:
            print(f'테스트 {t}를 통과하지 못했습니다.')
        print('-'* 40)
 
 

 

• sorted 함수의 key 파라미터로 functools.cmp_to_key(함수명)을 사용하며, element의 정렬 조건을 함수로 설정하게 된다. 또한 내림차순 정렬을 사용하기 위해 reverse = True
• 예외 입력으로 [0,0,0,0,0,0]의 형태일때, 결과는 "0"이 나와야 프로그래머스 사이트의 테스트 11번을 통과할 수 있다. 따라서 이를 해결하기 위해 answer = str(int(''.join(n))) 의 코드를 구성한다.

----------------------------------------
input -> ['6', '10', '2']
comparator: 10,2 -> 102,210 -> -1
comparator: 6,10 -> 610,106 -> 1
comparator: 6,2 -> 62,26 -> 1
n -> ['6', '2', '10']
answer :6210 / correct_answer :6210
테스트 0를 통과하였습니다.
----------------------------------------
input -> ['3', '30', '34', '5', '9']
comparator: 5,9 -> 59,95 -> -1
comparator: 34,5 -> 345,534 -> -1
comparator: 30,34 -> 3034,3430 -> -1
comparator: 3,30 -> 330,303 -> 1
comparator: 3,5 -> 35,53 -> -1
comparator: 3,34 -> 334,343 -> -1
comparator: 3,30 -> 330,303 -> 1
n -> ['9', '5', '34', '3', '30']
answer :9534330 / correct_answer :9534330
테스트 1를 통과하였습니다.
----------------------------------------
input -> ['0', '0', '0', '0', '0', '0']
comparator: 0,0 -> 00,00 -> 0
comparator: 0,0 -> 00,00 -> 0
comparator: 0,0 -> 00,00 -> 0
comparator: 0,0 -> 00,00 -> 0
comparator: 0,0 -> 00,00 -> 0
n -> ['0', '0', '0', '0', '0', '0']
answer :0 / correct_answer :0
테스트 2를 통과하였습니다.
----------------------------------------
 
Process finished with exit code 0
 

 

---

REF

def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K:
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K