Sort - 가장 큰 수** (Lv.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"

 

<My Source Code 1>

import itertools
def solution(numbers):
    answer = ''
    result = ''
    numberPermu = list(itertools.permutations(numbers))
    resultList = []
    
    for numList in numberPermu:
        for num in numList:
            result += str(num)
            
        resultList.append(result)
        result = ""
    
    answer = max(list(map(int, resultList)))
    return str(answer)

제일 처음 내가 테스트 돌려본 소스코드다.

itertools 패키지의 permutations 함수를 사용해 순열을 구한 뒤, 각각의 리스트를 결합하여 그 중에서 가장 큰 수를 return하는 방식이었다.

 

하지만 '시간초과' ...

이제는 한번에 성공하리라는 기대가 없다... ㅜ.ㅜ 언젠가는 나도...

 

어쨌든 왠지 찾아보니 나랑 동일하게 풀이한 사람에 따르면 Permutations는 모든 경우의 수를 찾아서 그렇다고 한다... 그래서 시간 초과가 나오는듯!!

 

어떤 방법으로 푸어야 할까...?

또 골똘히 고민해본다.

 

<My Source Code 2>

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

아무리 생각해도 논리적으로 떠오르지 않아 결국 다른 사람이 한 풀이 방식을 찾아보았다.

핵심은 lambda x : 3*x 이 부분이다.

 

numbers = [3, 30, 34, 5, 9] 일때, 

 

가장 깊게 고려해야하는 부분이 3, 30, 34 이 세트이다.

이 세가지를 이용해 만들 수 있는 조합은 

3-30-34

30-34-3

34-3-30

34-30-3

3-34-30

30-3-34

이렇게 3가지이다. 

앞자리 수는 3으로 동일하기 때문에 뒷자리 수가 무엇이 오느냐에 따라 달라지는 것이다.

그럼 한번 비교를 해보자.

 

일단 3, 30, 34 중에 제일 먼저와야하는 것은 34일 것이다. 

그럼 그 뒤에 무엇이 오는 것이 좋을까??

34303?  34330?

바로 34330이다. 즉 34 > 3 > 30 인것이다.

그리고 여기에 '문자열의 곱'의 특성과 조건 "numbers의 원소는 0 이상 1,000 이하입니다."을 고려하면,

3자리 수를 만들어 문자열의 크기를 비교할 수 있도록 하는 것이다. 

 

즉, 343434 | 333 | 303030 각각의 문자열에 *3을 통해 3자리수로 만들어 크기를 비교하는 방법이다. 

이렇게 한다고 한들 크기 비교 결과는 동일하다.

 

----1----

다른 예를 통해 크기를 비교해보자.

 

[23, 242, 2, 20]

 

첫번째 숫자는 2로 모두 동일하고 다음 두번째 수가 뭐가 오느냐에 따라 달라진다. 

23, 242, 20 중에서는 4가 오는 242가 먼저오는게 가장 큰 수가 될 수 있는 방법이다.

 

그럼 2는?

2가 앞에 오면 다음에는 어떤 숫자가 오던간에 2로 시작하는 숫자가 올 것이다. 

따라서 22로 봐도 무방하다.

 

참고로 2 == 22는 대수적으로는 성립하지 않지만 문자열의 특성을 고려하면 이렇게 봐도 무방하다는 것이다.

이부분을 습득하는데 애먹었다...

 

즉, 2 뒤에 0, 2, 3, 4 이 네가지 숫자가 올수 있는데 이중에서 제일 큰것은 단연 4이다.

 

그럼 첫번째는 242 - [23, 2, 20]

242다음에 올 숫자는 앞선 내용과 동일하게 23, 22, 20의 비교로 봐도된다.

즉 23이 오는 것이 맞다.

 

다음 2, 20도 같은 논리로 보면 22와 20이므로 2가 먼저 다음으로 20이 오는 것이맞다.

 

즉, 242 23, 2, 20 순서로 온 숫자의 합이 가장 큰 수가 되는 것이다.

 

이를 정리해보면, 결국 이 숫자들의 비교는 242242242 | 222 | 232323 | 202020 (242, 222, 232, 202)의 비교로도 가장 큰 수를 구할 수 있다.

 

----2----

이는 앞자리가 다르더라도 성립한다.

 

[20, 12, 7] 이 세가지를 통해 비교해보면, 202020 | 121212 | 777 (202, 121, 777)으로 777(7) -> 202(20) -> 121(12) 순서로 오는 것이 가장 큰 것을 알 수 있다.