11. 가장 큰 수 ★★ (정렬)

유형 : 정렬

풀이 시간 : 인터넷 검색

 

1. 나의 풀이

처음에는 permutation을 사용해서 풀이를 시도했다. 

from itertools import permutations
def solution(numbers):
    answer = ''
    num = [str(x) for x in numbers]
    ans = []
    for i in permutations(num):
        ans.append(''.join(list(i)))
    ans.sort(reverse = True)
    return ans[0]

 

그러나 정답은 int의 범위를 벗어날 수 있다고 되어 있었고, 

이는 곧 정수 정렬을 사용할 수 없다는 의미이다.

이 코드에서처럼 문자열 정렬을 하는 것은 큰 수를 찾는 데에 의미가 전혀 없다는 것을 알 수 있었다. 

제출했을 때에도 역시 정답이 아니었다. 

 

2. 문자열 정렬

문자열로 string을 사전 순으로 정렬하면 되지 않을까, 해서 시도해 보았다. 

def solution(numbers):
    num = [str(x) for x in numbers]
    num.sort(reverse = True)
    return ''.join(num)

그러나 여기에는 큰 문제가 있다. 

자릿수가 같은 정수는 잘 정렬될 것이지만,

사전순 정렬했을 때 가장 큰 수를 만들기 위해서는 

[34, 3, 30] 과 같이 정렬되어야 할 것인데, 사전순으로 정렬하면 [34, 30, 3] 으로 정렬된다는 것이다.

이 문제를 해결할 방법을 열심히 생각해봤지만 떠오르지 않아 결국 인터넷 검색을 해 보았다. 

 

 

<정답 풀이>

def solution(numbers):
    num = [str(x)*3 for x in numbers]
    num.sort(reverse = True)
    num = [x[:len(x)//3] for x in num]
    if num.count('0') == len(num):
        return '0'
    return ''.join(num)

 

솔루션은 의외로 간단했지만 아이디어를 스스로 떠올리지 못했다. 

[3434, 33, 3030] 이런 식으로 두 번 반복하게 되면 당연히 올바른 순서로 정렬이 될 것이다. 

3 하나가 있는 것은 결국 33이 있는 것과 같은 순서로 정렬이 되어야 하기 때문이다. 

 

=> 이 문제에서 주어진 배열에 들어있는 숫자의 크기는 1000 미만이므로 자릿수는 3자리

따라서 해결을 위해서는 3번 반복한 문자열을 정렬해 주면 된다. 

=> 그리고 모든 문자열이 0인 경우에 대한 예외 처리를 진행해 주면 된다.