[Programmers] Sort - 가장 큰 수 (Python)

출처ㅣ Programmers 코딩테스트 고득점 Kit

Sort: 가장 큰 수 [Lv2]

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

Solution

내 풀이

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))
    
    for i in range(len(numbers) - 1):
        for j in range(i + 1, len(numbers)):
            cmp1 = numbers[i] + numbers[j]
            cmp2 = numbers[j] + numbers[i]
            
            if cmp1 < cmp2:
                numbers[i], numbers[j] = numbers[j], numbers[i]
    
    answer = str(int(''.join(numbers)))

    return answer

시간초과로 실패했다.
이중 for문을 사용해서 두 수를 이어붙였을 때 어떤 순서로 붙여야 더 큰지 확인하는 방법으로 순서를 정했다.
마지막에 join을 사용하여 문자열로 만든 후 int형으로 바꾼 후 다시 문자열로 바꾼 이유는 numbers의 모든 원소가 0이면 0000과 같은 결과가 아닌 0으로 나오게 하기 위함이다.

결과

실패했다.. 밑의 코드를 확인하자.

Best Code

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

일단 numbers 안의 모든 원소를 string으로 바꿔 준다.(_numbers)
_numbers를 정렬시키는데, 원소값*3이 기준이고, 내림차순으로 정렬한다.
정렬할 때 기준을 원소값*3하는것이 핵심이다. numbers의 원소들을 모두 string으로 변환했기 때문에, 숫자 * 3이 아닌 문자로써 3번 반복한다는 뜻이다.
그리고 문제에서 numbers의 원소는 1000 이하라고 했기 때문에 최소 3자 이상으로 만들기 위해 3을 곱한 것이다. 자릿수를 맞춘 이유는 아래와 같은 방법으로 문자열을 비교하기 위해서이다.
정렬할 때에 문자를 비교할 때에는 ASCII코드값을 비교하여 순서를 정한다. 이 때에 문자열의 첫번째 문자부터 비교하여 점점 뒤로 가며 비교한다.
예를 들면 12와 1을 3씩 곱하여 비교해보자면 121212와 111을 비교하는 것이 된다. 첫번째의 1은 모두 같으므로 두번째를 비교한다. 그럼 2와 1을 비교하는 것이기에 12가 1보다 더 크다는 결론이 난다.
다른 예를 하나 더 들자면 11과 1을 비교해보자. 111111과 111을 비교하는데, 이 때에는 4번째 순서에서 111111은 1을 비교할 수 있고, 111에서는 더이상 가져올 수 있는 숫자가 없다. 그러므로 11보다 1이 더 작다는 결론이 난다.

결과

내가 푼 방법과 실행속도가 압도적으로 빠르다..
하 알고리즘.. 뿌셔..