[프로그래머스/Level2/파이썬3(python3)] 가장 큰 수

[프로그래머스/Level2/파이썬3(python3)] 가장 큰 수

문제

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):
    return str(int(''.join(sorted(list(map(str, numbers)), key=lambda x: x*3, reverse=True))))

설명

1차시도로는 itertools 패키지의 permutations(순열)함수를 사용해서 해당 수 조합으로 만들 수 있는 모든 수 조합을 만든 다음에 최대값을 리턴하는 식으로 만들었었다.

from itertools import permutations
def solution(numbers):
    max_number = 0
    for perm in list(permutations(numbers)):
        number = int("".join(map(str, perm)))
        if max_number < number:
            max_number = number
    return str(max_number)

이런식으로 말이다. 근데 다 시간초과뜨더라. 알고리즘을 찾아보니 permutations함수는 O(n!)의 시간복잡도를 갖고 있는데 아마 이 시간복잡도를 가진 함수는 통과하지 못하게 처리한 듯 싶다. 실제로도 O(n!)을 가진 함수는 지양해야 하니까. 그래서 다시 고민한게 위 풀이에 적힌 함수였다.
 하지만 저 함수를 만드는 데에도 고난이 있었다. 주어진 숫자들을 배치해서 큰 숫자로 만드는 데에는 성공했었다. 그냥 주어진 숫자들 중 큰 숫자를 앞에 배치하는 방식이었다. 하지만 반대케이스가 있었는데 주어진 입출력 예에서 볼 수 있다시피 30과 3이 주어졌을 때 무조건 3이 앞에 와야 더 큰 숫자를 만들 수 있다. 여기에서 고민이 시작됐다. 만약에 앞의 숫자가 같고 뒤의 숫자가 0이면 해당 숫자들을 모아서 따로 조사하는 식으로 작성해야 하나? 머리가 아파왔다. 그리고 다른 답을 찾아봤고 명쾌하고 아름다운 방법을 찾아냈다. 바로 해당 문자열을 3번 반복해서 비교하는 것이었다. 저 위에 적인 lambda부분에 x*3이라 적힌 부분이라고 보면 된다.
 원리는 이렇다. 예를 들어 90, 9가 매개변수로 주어졌다고 해보자. 그러면 9를 앞에 오게 해야하는데 단순비교를 하면 문자열로 비교를 하든 숫자로 비교를 하든 90이 더 크기 때문에 만들어지는 숫자는 909가 된다. 하지만 이것을 세번 반복한 문자열로 비교해보자. 그러면 909090과 999의 비교가 된다. 문자열의 정렬은 ASCII값으로 되고, 만약 앞글자에서 고저가 정해지면 뒤는 비교하지 않는다. 예로 설명하자면 사실상 90과 99의 비교가 된다는 얘기다. 맨 처음의 9는 똑같고, 두번째 글자에서 0(ASCII: 48)과 9(ASCII: 57)를 비교하게 되는데 여기에서 999를 더 큰 숫자로 인식하게 되어 90의 앞에 위치하게 만든다. 그렇게 990이 만들어지게 되는 것이다. 세번 반복하는 이유는 제한사항에서 원소의 크기가 최대 1000으로 정해졌기 때문이다. 990과 9라는 숫자가 주어지면 990이 더 큰수로 인식되니 단순 내림차순으로 정렬하면 9909라는 수가 만들어진다. 하지만 해당 조건에서 만들 수 있는 가장 큰 수는 9990이다. 세번 반복돼야 다른 자릿수를 가진 요소들과 혼동되지 않는다는 말이다.
 정말 세련되고 멋진 방법이다. 감탄, 감동했다.