[정렬/파이썬] 프로그래머스 lv2. 가장 큰 수 (feat. sort 메서드)

문제

숫자로 이루어진 배열을 조합해 가장 큰 수를 만들어라

주의

from itertools import combinations, permutations

 

순열이나 조합을 그대로 사용하면, 시간초과가 뜬다.

결정적인 차이

내코드

numbers.sort(key=lambda x: str(x), reverse=True)

 

>>> [9, 5, 34, 30, 3]

sorting 키를 사전순으로 함.

참고코드

nums_s.sort(key=lambda n : n*3, reverse=True)

참고 블로그

>>> [9, 5, 34, 3, 30]

sorting 키를 x3한 숫자의 사전순으로 함.

3이 30보다 먼저 나와야 330 > 303 으로, 더 큰 수를 만들기 위한 정렬이다.
*3 (곱하기 3) 이 왜 필요하냐면, 1000이하의 수로 이루어진 배열이기 때문에 한자리 수가 세자리 정도로 나와야 비교할 수 있다.
int에 *3이 아니고, str에 *3이라 배열에 *3을 한 리스트는 [999, 555, 343434, 303030, 333] 이러한 모양으로 나오게 된다.

전체 코드

def solution(numbers):
    nums_s = [str(num) for num in numbers]
    nums_s.sort(key=lambda n : n*3, reverse=True)
    ans = str(int(''.join(nums_s)))

    return ans

.sort() 메서드

.sort(key = lambda x: x) 는 꼭 기억해야 한다!

+ 왜 굳이 3인지 부가 설명

만약, numbers가 [221,2,10] 이렇게 주어졌다고 가정했을때 정렬이 끝나면 [2,221,10] 순서가 되어야한다.

1. x*2를 하면,
   >>> [221221,22,1010]
   이렇게 되면 22보다 221이 문자열로 비교했을 때, 더 큰수로 나오기 때문에 원하는 정렬이 되지 않습니다.
2. x*3 하면,
   >>> [221221221,222,101010]
   문자열로 봤을 때, 222 > 221221221 이 성립하므로, [2,221,10] 순서로 정렬할 수 있게 된다.

1000이하의 숫자끼리 비교를 해야 하는 조건이기 때문에 x3을 해줘야 하고, 만약 10,000이하의 조건이라면 최소한 x4를 해줘야 원하는 순서로 정렬할 수 있게 된다.