[Programmers]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 합니다.

 

코드

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

 

진행 과정

 

예제 #1

numbers = [3, 30, 34, 5, 9]

 

자릿수가 같은 숫자들은 string으로 변환하고 비교하면 된다. 그런데 자릿수가 다른 숫자 "3" , "30"같은 숫자는 어떻게 비교를 해야할까?

 

간단히 생각하면 서로 자릿수를 맞추고 비교하면 된다. 하지만 이 과정에서 서로 자릿수를 비교하고 숫자를 추가하면서 시간복잡도가 늘어나며 시간초과가 뜨기도 한다.

 

해당 문제 제한사항에서 "numbers의 원소는 0 이상 1,000 이하입니다."라는 사항을 이용하여 한 자리 숫자라면 string으로 변환 후 * 3을 한다. 두 자리 숫자, 세 자리 숫자라고 해도 똑같이 * 3을 하는데 예를 들어 "30"이라고 한다면 "303030"이 될것이다. 그리고 * 3을 실행한 "333"과 비교해보면 (3,3), (3,0)... 으로 두번째 숫자에서 "333"이 더 크므로 "3"이 더 큰 숫자라고 판단된다. 세 자리 숫자도 마찬가지이다.

 

따라서 모든 요소를 string으로 변환 후 key 값을 람다식 x * 3으로 지정하여 내림차순 정렬을 실행하면 되는 것이다. 또는 람다식 (x * 3)[:4]로 지정하여 모든 숫자를 네 자리로 맞춰주어도 똑같이 정답처리가 된다.

 

코드 진행은 sort 하나 밖에 없기때문에 생략한다.