[Programmers] 정렬 - 가장 큰 수 찾기

문제

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

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

My Solution (Time Out)

Idea1 : Permutation 이용

• 모든 순열에 대해 시도 ⇒ Time Out

from itertools import permutations

def solution(numbers):
    answer = []
    for case in permutations(numbers, len(numbers)):
        answer.append(''.join(map(str,case)))
            
    return max(answer)

• 결과 : 26.1 / 100
  ⇒ 정렬을 이용한 방법 필요…

Other’s Soultion

• 출처 : https://liveloper-jay.tistory.com/138

핵심 아이디어

1. 각 수를 3번 반복한뒤 합친다.
   • 왜 3번 반복? : 제한 사항 중 numbers 의 범위가 1000 이하이다.
2. 2번에서 구한 앞 3자리수 순으로 기존 리스트를 내림차순 정렬한다.
   • point. 문자열의 정렬 방식을 이용하여 내림차순 정렬

예시

어떻게 하면 [321, 39, 3, 12] 에서 [39, 3, 321, 12] 로 정렬할 수 있을까?

1. [321321321, 393939, 333, 121212]
2. 1에서 구한 리스트 기준으로 [321, 39, 3, 12] 정렬

구현

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers)) # str 변환
    ''' 
    1. 3번 반복뒤 합친다.
    2. 1번에서 구한 값을 기준으로 기존 리스트(numbers)를 내림차순으로 정렬한다.
    '''
    numbers.sort(key= lambda x : (x*3), reverse=True) 
    
    for number in numbers:
        answer += number
    
    return str(int(answer)) # [0, 0] case -> 00 (X) -> 0 (O)