가장 큰 수, Python3 원리 [프로그래머스]

 

문제 설명

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

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

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

제한 사항

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

입출력 예

numbersreturn

[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

---

이건 정말 감이 안잡혀서... 사실 할 수 있었지만

개노가다로 하는 것은 아닌 것 같아서 구글링했다.

 

def solution(numbers):

    numbers = list(map(str, numbers))

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

    return str(int(''.join(numbers)))

 

원리는

숫자의 정렬과 문자열의 정렬의 차이다.

 

숫자의 정렬은 기본적으로 크기순으로 정렬된다.

 

문자열의 정렬도 순서대로 정리된다. 하지만 ASCII코드 순으로 정리된다.

예를 들어

 

 

첫번째 자리에서 ASCII 코드가 가장 먼저나오는 사람? 

다 같이 1이 나오네?

 

두번째 자리에서 가장먼저나오는 사람?

1은 한자리네 ? 1나옴

그래도 0이 2,4보다 먼저나옴

10

 

세번째 자리에서 가장 먼저 나오는 사람?

14 전 그래도 두자리네요

 

그다음 123

 

이런식이다.

 

숫자의 크기에 상관없이.. 같은 자리일 때 숫자가 작은게 먼저나온다.

**ASCII코드는 0123456789 순이다.

 

하지만 우리 입맛대로 정렬하기 위해선

34와 3의 비교가 안되니

자리를 늘려서 이용했다. 

343434,333, 303030

 

이 아이디어는 어떻게 생각한건지 ㅋㅋㅋ

게다가 33과 3의 충돌이면 자리수가 더 적은게 우선이다... ㅎ 진짜 딱 떨어진다.

 

import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

 

하지만 이렇게 풀 수도 있다고 한다.