[Programmers] the largest number.py (sort)

#. Problem

https://programmers.co.kr/learn/courses/30/lessons/42746

* The copyright in this matter is in Programmers

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - 정수를 이어붙여 만들 수 있는 가장 큰 수

    - 문자열로 바꾸어 return

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 첫 자리가 가장 큰 수가 앞으로 와야 큰 수가 만들어질 수 있음

     (첫 자리 수를 비교하여 가장 큰 수부터 꺼내옴. 

      단, 첫 자리수가 같을 경우 둘째 자리 수를 비교, 둘째 자리가 없다면 첫 자리 수와 동일하게 취급)

  2. 문자열로 바꾸어 return

  1. python에서 문자열인 숫자도 비교할 수 있다는 것을 알면 편하다.

    더 중요한 것은 문자열로 된 숫자를 비교할 때, 왼쪽부터 문자인 숫자 대소를 비교한다.

    즉, '335' 와 '333333'을 비교하면 '335'가 더 크다는 것이다 ! 

    왜냐하면 왼쪽부터 문자인 숫자 대소를 비교하면 세 번째 수인 5가 3보다 크기 때문이다.

    문제는 한자리수를 비교하는 것.

    중요한건 가장 큰 수를 만드는 것 이므로, 가장 큰 수를 만들 때 '3'과 '322'가 있다면 '3322' '3223' 을 비교해보자.

    여기서 '3'이 '322'보다 먼저 나와야 큰 수가 만들어질 수 있다. 반면 '3'과 '344'가 있다면 '3344' '3443' 을 비교해보자.

    여기서는 '344'가 먼저 나와야 큰 수가 만들어진다.

 

    결과적으로! '3'을 '333'으로 생각하고 비교해도 위와 동일하다는 것이다. '333' > '322' , '333' < '344'

    문제에서 numbers의 원소는 0이상 1,000이하이므로,

    한자리 수를 포함해서 모든 문자열인 숫자를 3배로 늘려주어도 비교에 문제를 일으키지 않는다.

    '3' -> '333'

    '32' -> '323232'

    '345' -> '345345345'

#. Code

1 2 3 4 5

def solution(numbers):     num = list(map(lambda x:str(x)*3, numbers))     num.sort(reverse=True)     res = list(map(lambda x:x[:(len(x)//3)], num))     return str(int((''.join(res))))

cs

  - numbers의 문자열들을 3배로 늘려주고,

    내림차순으로 정렬.

    다시 numbers의 문자열들을 복구시켜준 후 

    list의 요소들을 문자열로 합쳐줌 (0이라는 예외처리를 방지하기 위해 int로 변환 후 다시 str로 변환하는 작업이 필요)

#. Other code

1 2 3 4

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

cs

  - str을 3배로 늘리고 다시 줄여주는 작업을 sort 함수의 key 옵션을 통해 더 간결하게 작성