프로그래머스 - 가장 큰수(정렬) / Level 2

문제 설명

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"

 

풀이

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

 

이 문제는 고민하다 결국 풀지 못하여 널리 알려진 다른 풀이법을 보며 공부해보겠다.

먼저 가장 첫 번째로 해야 되는 생각은 리스트 내의 숫자들을 비교할 때 자릿수 별로 나눠서 비교해야 되기 때문에

문자열로 변환시켜된다는 생각이다.

 

그다음 이 문제의 가장 중요한 key point가 되는 아이디어는 바로 "x*3" 이 부분이다.

비교할 때 문자열을 3배 해서 비교해주겠다는 것인데 

앞선 예시를 가져와 설명해보면 ["6", "10", "2"]와 같은 상태에서 각각을 비교하는 것이 아니라

["666", "101010", "222"]와 같은 상태에서 비교를 진행한다는 것이다.

 

그렇게 하는 이유는 문자열 sort의 특징과 numbers의 원소가 최대 세 자릿수 이기 때문이다.

sort()에서 문자열을 비교할 때 사전 순으로 비교하는데 이것은 문자열에서 순서대로 하나씩 문자를 아스키 값으로 변환하여 비교한다는 것이다. 

즉, 숫자들을 자릿수 별로 비교할 수 있다는 것이고 가장 작은 한 자릿수가 세 자릿수와 모든 자릿수를 비교할 수 있도록

3배(문자열 3배) 해준 것이다. 어차피 앞의 세 자리로 다 구분되기 때문에 뒤에 늘어난 숫자들에 대해선 상관할 필요 없다.

 

마지막에 str(int()) 이런 식으로 구현한 부분은 "0000"과 같은 경우를 "0"으로 표현하기 위한 것이다.