정렬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 합니다.
입출력 예
numbers return
[6, 10, 2] "6210"
[3, 30, 34, 5, 9] "9534330"

풀이

풀이 1 permuntation 시간초과

def solution(numbers):
    answer = ''
    perm = list(permutations(numbers, len(numbers)))
    permList = [''.join(map(str,i)) for i in perm]
    answer = max(permList)
    return answer

풀이 2 len으로 나눈 나머지로 비교

-> 34 30 3 이 남았을 경우, 조합이 34303 이 아닌 34330 이 되야 함, 따라서 틀린 풀이였다.

풀이3. lamda로 전체 자릿수를 맞춰준 뒤 비교를 통해 이를 해결.

def solution(numbers):
    numbers = list(map(str, numbers)) 
    return str(int(''.join(numbers))) # e.g. '0000'을 '0'로 바꿔주기 위함

• str 기준으로 비교, 숫자의 앞자리로 비교하기 위함
  numbers.sort(key=lambda x: x*3, reverse=True) # 숫자 뒤에 0이 들어가는 경우 순서를 뒤로하기 위함
• 문자 x 에 3을 곱하면 xxx 이다. 3을 곱하는 이유는 입력받는 숫자의 자리가 1000이하의 자리이기 때문이다.
• 따라서 30 과 34와 3을 비교하면,
• 303030 VS 343434 VS 333 이 되는 것이다.
• 문자열 비교연산의 경우엔 첫번째 인덱스인 666[0]인 6과 101010[0]인 1과 222[0]인 2를 ascii숫자로 바꿔서 비교한다.
• 물론 같으면, 다음 인덱스도 비교한다. 비교한 결과 [34, 3, 10]의 순으로 정렬된다.

코드

def solution(numbers):
    
    numbers = list(map(str, numbers)) # str 기준으로 비교, 숫자의 앞자리로 비교하기 위함

    numbers.sort(key=lambda x: x*3, reverse=True) # 숫자 뒤에 0이 들어가는 경우 순서를 뒤로하기 위함
    return str(int(''.join(numbers))) # e.g. '0000'을 '0'로 바꿔주기 위함

배운것

• lambda 함수
• lambda 함수 sort 할때 key값에 사용
• 문자 크기비교는 ascii 코드로 가장 앞의 숫자만 비교
• 문자 * 3 은 > 문자문자문자