문제 설명
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 |
내 코드
from itertools import permutations
def solution(numbers):
numbers = list(map(str, numbers))
p_num = list(permutations(numbers))
num_list = []
for i in range(len(p_num)):
num_list.append(''.join(p_num[i]))
return str(max(num_list))검색을 통해 permutations로 경우의 수에 해당하는 것들을 다 만들 수 있다는 것을 알고 모든 숫자들을 만들고 max값을 구하는 코드를 구현하였다.
하지만.. 테스트 1~11 〉 실패 (시간 초과)
아무래도 모든 값들을 경우의 수에 따라 생성하고 max로 다 돌려봐야해서 그런 것 같다.
이틀동안 이리 저리 생각해봤지만 해결되지 않아서 이번에만 다른 사람의 코드를 보고 공부해야겠다...
다른 사람의 생각
Ascii 코드표를 이용한 코드
def solution(num):
num = list(map(str, num))
num.sort(key=lambda x: x * 3, reverse=True)
return str(int(''.join(num)))정말 이렇게 간단할 줄 상상도 못했다.
1. 먼저 num 리스트의 값을 str으로 바꿔주고, 정렬을 한다.
2. lambda x: x * 3 은 위에서 num의 인수값이 1000 이하이므로 한 자릿수의 수를 세 자릿수로 맞춘 뒤 비교한다는 뜻이다. 즉 [666, 101010, 222]의 첫 번째 자릿 값을 비교하게 된다.
3. str(int()) 를 하는 이유는 만약 numbers = [0, 0, 0, 0] 이라면 그냥 조인 하면 0000 이 답으로 출력되는데 이를 0으로 만들기 위해 이렇게 작성한다.
functools를 이용한 코드
import functools
def comparator(a,b):
t1 = a+b
t2 = b+a
return (int(t1) > int(t2)) - (int(t1) < int(t2)) # t1이 크다면 1 // t2가 크다면 -1 // 같으면 0
def solution(numbers):
n = [str(x) for x in numbers]
n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
answer = str(int(''.join(n)))
return answerfunctools의 cmp_to_key는 처음 보는 메서드인데, 파이썬 3.9.1 문서 에 따르면 다음과 같다:
비교 함수는 두 개의 인자를 받아들이고, 그들을 비교하여, 작으면 음수, 같으면 0, 크면 양수를 반환하는 콜러블입니다. 키 함수는 하나의 인자를 받아들이고 정렬 키로 사용할 다른 값을 반환하는 콜러블입니다.
즉, 위에서 만든 compator 함수로 얻어진 값을 바탕으로 정렬을 한다고 생각할 수 있다.
