[프로그래머스] 가장 큰 수

https://programmers.co.kr/learn/courses/30/lessons/42746?language=python3 

코딩테스트 연습 - 가장 큰 수

문제를 파악해보자. 0 또는 양의 정수가 주어졌을때 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내는 문제이다. 제한 사항을 보면 

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

와 같은 것들이 있다. 우선 기본적인 원리를 생각해보자.

• 문자열로 반환을 해주어야 하므로, 정수 형태의 요소들을 문자열로 변환해 주어야 한다.
• 최대한 큰 수를 만들어야 하므로, 내림차순 정렬을 해준 후에 문자열을 생성해 주어야한다
• 정렬을 위해서는 기준점을 각 숫자의 첫번째 값으로 해주어야한다. 맨 앞자리 값이 같은 원소끼리 비교를 해주어야한다.

파이썬에서는 문자열 비교를 할때 각 자리수를 아스키로 변환해서 비교하게 된다. 각 자리수 별로 아스키를 비교하면서 정렬을 한다. 동일한 아스키 값의 문자인 경우에는, 동일한 값으로 아닌 경우에는 아스키 비교로 크기 비교를 하는것이다. 아래 사진을 살펴보자

두번째 사진을 보면 확실히 알 수 있다. 앞에 40까지는 동일하지만, 뒤에 a,b,c가 다르다. 이런 경우 a,b,c의 아스키값을 가지고 비교를 하게 된다. 또 세번째 사진을 보게 되면 40ba와 40baz에 대해서, 40ba에 비해 40baz가 아스키 적으로 하나의 값이 더 있기 때문에, 뒤로 가는것을 알 수 있다. 

 

이 원리를 문제에 접목시켜보면, numbers의 각 원소는 0~1000사이이므로, 최소 1자리, 최대 3자리를 가지게 된다. 그렇기 때문에 이를 비교하기 위해서는, 자리수를 맞춰주어야 한다. 이때 최대 자리 수인 3자리를 맞춰준 후 비교를 해주면 된다. 

from itertools import permutations
from typing import MutableSequence

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