[프로그래머스 | 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 합니다.

입출력 예numbersreturn

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

 

 

 

문제풀이

문자열 길이를 3배로 늘린 후에 비교하는 방식 ( 원소가 1000이하 ) 

 - 문자열에서의 대소비교와 일반숫자의 대소비교가 다르기때문에 가능

 - 예를들어 '121'과 '12'의 경우 12가 더 먼저와야 큰수를 만들 수 있는데, 

 - 문자열 비교에서 '121121121'과 '121212'가 더 큰수이기 때문이다.

 

제일 설명을 잘하신 블로그 부분 발췌

출처 : https://huidea.tistory.com/4

 

가령 [3,300,31,387] 라는 숫자 리스트가 있다면 가장 큰 조합은 --> 387 3 31 310 이다. 

가장 작은 수가 3 이더라도, 첫째자리 숫자 "3"은  310 31 의 두번째 자리 숫자 "1" 보다 크기 때문에, 3은 310 31 보다 앞에 나온다. 

또 31은 31의 두번째 자리숫자 "1" 이 310 의 세번째 자리 숫자 "0" 보다 크기 때문에, 310 보다 앞에 나온다. 

3 >31, 310	31 >310
3  31 310	31 310

따라서 비교 하는 숫자들의 자리수를 맞춰?서 비교를 해보기 위해 문자열 곱셈을 하여 숫자의 길이를 늘렸다. 

3 ----> 3 3 3
31  -->  3 1 3 1 3 1
310 -> 3 1 0 3 1 0 3 1 0

 

3번씩 써서 늘리는 이유는 문제 조건에서 입력되는 숫자의 최대 크기가 1000미만이라 제시했기 때문이다.

따라서 입력되는 숫자의 최소길이는 1자리 최대길이는 3자리 일것이고, 1자리 숫자를 3자리로 불려줌으로써 

문자형태의 숫자를 대소비교한다.

 

def solution(numbers):
    answer = ''
    
    num_list = list(map(str, numbers))
    
    #문자열 길이를 3배로 늘린 후에 비교
    num_list.sort(key = lambda x:x*3, reverse=True)
    answer = "".join(num_list)
    return str(int(answer))