[프로그래머스] 가장 큰 수 (level2, 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 합니다.

---

입출력 예

---

풀이 코드

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

 

핵심적인 아이디어가 없으면 풀이하기 어렵다.

우선, 문자열의 사전적 정렬을 하게 되면 앞 자리 수가 높은 수로 정렬이 가능하다.

문제는, 30과 3의 순서이다. 303이 아니라, 330이 되어야 하는데 reverse = True를 적용하면 303이 된다.

그렇다고 reverse를 주지 않으면 오름차순 정렬이 되기 때문에 1이 9보다 먼저 나올 것이다.

 

여기서 핵심 키워드는,

• numbers의 원소는 0 이상 1,000 이하입니다.

이 조건이다.

 

만약에 키를, 해당 문자열을 3번 복사한 것을 기준으로 정렬을 한다고 치자.

32와 3은, '323232'와 '333'을 비교한다.

내림차순 사전식 정렬을 한다면, 두 번째 자리의 3이 더 크므로 3이 32보다 앞으로 오게 된다.

 

34와 3은, '343434'와 '333'을 비교하면,

두 번째 자리의 '4'가 더 크므로 34가 3의 앞으로 오게 된다.

 

따라서 기존에 정렬하려고 했던 방향을 모두 지키면서 정렬이 가능하다.