[프로그래머스/파이썬] 가장 큰 수

문제 설명

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"

1. 각 원소를 순회하며 모든 경우의 수에 대한 숫자 배열 생성
2. sort로 숫자 정렬
3. 가장 큰 숫자 리턴

 

from itertools import permutations

def solution(numbers):
    length = len(numbers)
    res = []
    tmp = list(permutations(numbers, length))
    for i in range(len(tmp)):
            res.append(int(''.join(map(str,tmp[i]))))
    res.sort()
    
    return str(res[-1])

아무대로 permutations 함수를 사용해서 시간 초과가 나는 것 같습니다.

순열이기 때문에 O(n!)의 시간 복잡도를 가지게 되고, 이로 인해 시간 초과가 나는 것 같았습니다.

따라서 시간 복잡도를 줄이기 위해서는 최소한의 비교를 통해 결과를 알아내야합니다.

 

heapq로 정렬하는 등 다른 방법들을 생각해보았는데, 결국 떠오르는 방법이 없어 다른 풀이를 참고하였습니다.

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

진짜 코드 처음봤을 때 천재인가 싶었습니다..ㅎㅎ

 

이 코드의 특징은 문자열임을 이용하는 것입니다.

 

만약 [3, 30, 34, 5, 9] 라는 배열이 주어졌는데, 문자열 변환 없이 int로만 비교하였다면 당연히 틀린 값이 나왔을 겁니다.

하지만 문자열로 변환하여 ["3", "30", "34", "5", "9"] 이러한 값이 되게 되고, sort의 키 값을 x+x+x로 주게됨으로써 가장 앞의 숫자부터 비교를 하게됩니다.

 

"3" -> "333" "30" -> "303030" "34" -> "343434" "5" -> "555" "9" -> "999"

정렬 시에 위 값들이 비교되게 되는데, 문자열은 가장 앞부터 큰 값을 비교하기 때문에 9, 5, 34, 3, 30 순으로 정렬이 되게 됩니다.

 

 

또한 세번 더하는 이유는 만약 최대 1000이라는 조건이 주어졌기 때문입니다.

 

두번 더했을 때를 가정하고 반례를 제시해보겠습니다.

[991,9,30] ⇒ [991991, 99, 3030]

991, 9, 30 순으로 정렬이 되게 되고, 가장 큰 값은 991930으로 판별되게 됩니다. 하지만 사실 가장 큰 값은 999130입니다.

 

위 반례에 대해 세번을 더하면 아래와 같은 결과가 나옵니다.

[991,9,30] ⇒ [991991991, 999, 303030]

9 , 991, 30 순으로 정렬이 되고, 가장 큰 값은 999130입니다.

 

즉, 가장 큰 원소의 자릿수에 맞춰 각 자리를 비교하기 위해 가장 작은 원소의 자릿수를 가장 큰 원소의 자릿수와 맞추는 과정이 필요합니다.

 

 

 

---

비록 제가 permutations를 사용하여 시간 초과가 났지만, 아래 블로그에 사용법이 잘 정리되어있어 함께 첨부합니다.

https://ourcstory.tistory.com/414