문제 풀이

먼저 주어진 수들을 합칠 수 있는 방법을 모두 나열한 뒤 가장 큰 값을 찾는 것은 안됩니다. 제한 사항에 "numbers의 길이는 1 이상 100,000 이하입니다."가 있기 때문에 최악의 경우 100000!만큼 연산을 해야 하고 이는 시간 초과를 발생시킬 수 있는 너무나 큰 숫자 입니다.

STEP 1

가장 큰 수가 나오기 위해서는 각 numbers의 원소들의 가장 맨 앞자리 수가 큰 순서로 정렬을 하면 됩니다. [3, 30, 34, 5, 9] 문제의 예시처럼 이 경우 맨 앞자리 수가 9가 제일 크므로 9를 먼저 놓고 그 다음 5를 놓습니다. 이 부분은 정수 배열을 문자열 배열로 바꾼 뒤 정렬하면 해결됩니다. 왜냐하면 문자열은 맨 첫 글자의 아스키코드 값을 기준으로 정렬하기 때문입니다.

STEP 2

문제는 3과 30, 34 입니다. 3개의 숫자 모두 앞자리가 3으로 동일하지만 3과 30중에는 3이 앞에 와야합니다. 왜냐하면 303일 경우와 330과 같은 경우가 만들어지기 때문입니다. 즉 3은 33이하의 숫자보다는 우선순위를 크게 가져야 합니다. [3, 32], [3, 31], [3, 30]의 경우 등을 생각해보면 됩니다. 이러한 경우 어떻게 해결해야 할까요?

바로 원소를 3번 이어붙이는 것 입니다. "numbers의 원소는 0 이상 1,000 이하입니다." 해당 조건에서 우리는 모든 원소가 0~1000 에 속한다는 것을 알 수 있습니다. 따라서 3과 30을 비교할 때 3을 3번 이어 붙이면 333이 되고 30을 3번 이어 붙이면 303030이 됩니다. 이를 비교해보면 333문자열이 더 큰 것을 알 수 있고 이를 통해 333, 303030, 343434의 순서가 343434, 333, 303030이 되는 것을 알 수 있습니다.

lambda를 이용한 sort

위의 step2를 구현하기 위해서는 문자열을 3번 이어붙인 상태를 기준으로 정렬을 수행해야 합니다. 물론 3개를 이어붙인 배열을 하나 만들어 그 상태로 정렬을 수행해도 되지만 sort에서 lambda를 이용하면 사용자가 원하는 기준으로 정렬이 수행됩니다.

사용법은 다음과 같습니다. key 인자에 함수를 넘겨주면 해당 key 인자가 기준이 됩니다. 밑의 예시에서는 x[1]이 정렬의 기준이 됩니다. 또한 sort 함수는 기본적으로 오름차순으로 정렬되며 이는 reverse 인자에 의해 결정됩니다. reverse 인자는 기본적으로 False이므로 True로 바꾸어주면 내림차순으로 정렬을 수행합니다.

arr.sort(key = lambda x: x[1], reverse = True)

소스코드

def solution(numbers):
    str_numbers = []

    # 정수 배열을 문자열 배열로 바꾸어줌
    for num in numbers:
        str_numbers.append(str(num))

    # 문자열 배열을 원하는 기준으로 정렬
    str_numbers.sort(key = lambda x: x*3,reverse=True)

    # 모두 이어 붙임
    return str(int(''.join(str_numbers)))