[Python] (정렬) 가장 큰 수

문제 설명

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"

 

코드 작성

실패 #1

from itertools import permutations

def solution(numbers):
    permut = list(permutations(numbers, len(numbers)))
    
    number_list = []
    summ = ''
    
    for i in range(len(permut)):
        per = permut[i]
        for j in range(len(numbers)):
            summ += str(per[j])
        number_list.append(int(summ))
        summ = ''
    number_list.sort(reverse=True)
    answer = str(number_list[0])
    return answer

순열 함수를 썼는데, 시간초과떴다.

 

실패 #2

from itertools import permutations

def solution(numbers):
    numbers_str = list(map(str, numbers))
    permut = list(permutations(numbers_str, len(numbers)))
    
    number_list = []
    summ = []
    
    for per in permut:
        num = ''.join(per)
        summ.append(num)
        
    num_sum = list(map(int, summ))
    num_sum.sort()
    answer = str(num_sum[-1])
    
    return answer

아까보다 조금 빨라졌는데 아직 큰 데이터에는 시간초과가 생긴다.

예상하건데 순열을 만드는데 시간이 엄청 걸리는 것 같다.

 

 

한 1시간반 머리짜냈는데 모르겠다.

못풀겠다.

 

다른 사람 코드

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

• numbers를 map을 이용하여 str형태로 만든다.
• key매개변수로 람다를 두었다.
• x: x*3으로 두면 리스트안에 원소가 3번 곱해진다.  예를 들어 ['3', '9', '30', '18']이면 '333', '999', '303030', '181818'이 된다. 그리고 이것을 정렬하면 ['181818', '303030', '333', '999']이 된다. (문자형 숫자는 자릿수 별로 작은 숫자를 판별하여 정렬함). 마지막으로 reverse를 하면 ['999', '333', '303030', '181818']이 된다. 이것을 기준으로 numbers가 정렬되므로 결국 ['9', '3', '30', '18']로 정렬이 마무리된다.
• 구분자.join(리스트)를 사용하면 리스트에 있는 string 원소들 사이의 ', '를 없앨 수 있다. 따라서 '933018'이 된다. 이것을 int로 바꾸고 다시 str로 바꾸는 이유는 숫자가 0인 경우가 있기 때문이다.

 

끝으로

저런 생각은 어떻게 하는지 참.. 부럽기만 하다.