가장 큰 수 - 프로그래머스 Python

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

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

 

 

생각해 볼 점 
1. 순서를 재배치해서 가장 큰 수를 만들어라? →  n이 10만 이하라 전부 만들어보는 방법은 X
2. 그럼 남은 건 그리디 기반 정렬
3. 그냥 양의 정수가 아니라 0도 포함했다? 테케가 0으로만 있는 경우도 고려 해야 함. 

 

내 풀이: 

from functools import cmp_to_key
def solution(numbers):
    numbers = list(map(str, numbers))
    
    def compare(a,b):
        if a + b > b + a:
            return -1
        else: return 1
    
    numbers.sort(key=cmp_to_key(compare))
    
    return str(int("".join(numbers)))

처음에 리스트 안에 있는 걸 다 string 으로 바꿔주는 방법이 생각 안 나서 이렇게라도 풀었음... 

    stringy = ""
    for number in numbers:
        stringy += str(number)

그 뒤 list(map) 형식으로 바꿔서 훨씬 간편하게 바꿈. 

list에 있는 걸 전부 하나의 string으로 바꿀 때 join 쓰는 것도 아주 간편하다!

 

더 나은 다른 사람 풀이: 

출처:

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

프로그래머스

 

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

미친게 아닌가 싶다. 어떻게 이런 생각을 하지. 

string을 3번 곱하면 2 →  222 이렇게 더해진다. 

그리고나서 string 끼리 비교를 하면 더 큰 수가 이기는게 아니라 앞에서부터 한 자리씩 더 큰 수가 이기게 된다. 

222 > 221221221

이런 식으로.. 이걸 이용해서 만든 코드다.