[프로그래머스] 정렬: 가장 큰 수

문제 설명

 

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

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

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

제한 사항

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

 

입출력 예

 

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

 

 

나의 솔루션

 

이 문제의 핵심은 숫자가 크다고 해서 무조건 앞에 올 수 없다 는 점이었다.  가령 첫 번째 예시의 경우, 10이 가장 큰 수이지만 역설적으로 제일 앞에 오게 될 경우 만들 수 있는 조합 중 가장 작은 수가 만들어진다. 이처럼 단순 수의 대소비교를 할 것이 아니라, 오히려 다른 자료형의 특징을 살리는 것이 중요한 문제였다.

 

숫자간의 비교와 문자열로 표현된 숫자 간의 비교는 다르다. 간단히 정리하면, 숫자는 숫자 값 그대로 비교되나 문자열로 표현된 숫자 (가령 '5') 는 ascii 값으로 치환되어 사전식 순서가 비교된다. 예를 들어, 숫자 100은 숫자 11보다 큰 값이나, 문자열 100 은 문자열 11보다 사전적으로 앞에 있기 때문에 대소비교시 더 작은 값이 된다. 

 

이러한 특징을 이용하여, 문자열로 표현된 수들이 모두 기본적으로 사전식으로 정렬될 수 있도록 자릿수를 맞춰주면 된다. 문제에서는 모든 원소가 1000이하임을 밝혔으므로, 가장 작은 단위의 수가 될 한 자리 수가 가장 큰 단위의 수가 될 네 자리 수가 되도록 모든 원소에 4를 곱했다. 

 

예를 들어 '100' 과 '11' 을 비교하게 되더라도, '100100100100' 과 '11111111' 간의 비교를 통해 11이 더 앞에 와야 할 것임을 알 수 있게 된다. 

 

def solution(numbers):
    numbers = [str(n) for n in numbers]
    numbers = sorted(numbers, key=lambda x:x*4, reverse=True)
    return str(int(''.join(numbers)))

 

배운 점

python 의 lambda 함수는 굉장히 강력하다. 특히 고차함수 안의 콜백으로 전달될 때 그 위력이 더해지니 사용법을 익히고 자유자재로 활용해보자.