1. 문제

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

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

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

2. 제한사항

numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

3. 입출력 예시

4. 나의 풀이

(1) 브루트 포스

itertools 라이브러리의 permutations을 사용하여 만들 수 있는 모든 조합을 num_list안에 담은 후,
내장함수 max 를 사용해 가장 큰 수를 골라 string 형식으로 변환 후 return 해 줬다

from itertools import permutations
def solution(numbers):
    num_list = []
    permutation = list(permutations(numbers, len(numbers)))
    for i in permutation:
        num = ""
        for k in i:
            num += str(k)
        num_list.append(int(num))
    return str(max(num_list))

위 처럼 numbers 배열이 고작 5개여도 굉장히 많은 조합이 발생하기 때문에 시간 초과가 발생한다..

(2) sort 함수 이용

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

numbers안의 숫자를 앞에서부터 한 글자씩 비교를 해 주기위해, map을 이용하여 string 형식으로 바꿔 주었다
nubmers안의 숫자는 1000이하의 숫자이기 때문에, lambda를 이용하여 *3 을 해줌으로서 최소 자릿수를 3자리가 되도록 해줬다
ex) [6, 10, 2]의 경우에 [666, 101010, 222]
내림차순으로 정렬 해주기 위해 reverse=True를 해줬다
0이 중복되서 나온 수를 0으로 출력하기 위해 numbers안의 요소를 int형으로 변환 후, string형식으로 변환해서 출력

5. 전체 코드

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