[프로그래머스] 가장 큰 수 python

https://programmers.co.kr/learn/courses/30/lessons/42746

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

내가 푼 방법

처음에는 permutations 를 쓸려했으나 길이를 보고 시간제한때문에 안되겠다 생각함.

그 다음 자릿수별로 부동소숫점 이용하여 풀었음

def solution(numbers):
    num_f=[]
    for i in numbers:
        if i//10==0:
            num_f.append((str(i),0))
        elif 10>i//10>=1:
            num_f.append(('%.1f'%(i/10),1))
        elif 100>i//10>=10:
            num_f.append(('%.2f'%(i/100),2))
        else:
            num_f.append(('1.000',3))
    num_f.sort(key=lambda x: (-float(x[0]),x[1]))
    ans_list=[i[0] for i in num_f]
    answer=int(''.join(ans_list).replace('.',''))
    return str(answer)

아쉽게도 "9" ,"991" 과 같은 경우

9991 이 가장 큰 숫자이지만 9919 로 나와 틀렸고 이를 해결할 방법을 찾지 못했음.

그렇게 답을 찾아본 결과

 

정답 코드 1

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

깔끔하고 쉬워보이지만 내가 다음에 이 방법으로 풀수 있다는 생각 X

정답 코드 2

import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    
    #  t1이 크다면 -1  // t2가 크다면 1  //  같으면 0
    return (int(t1) < int(t2))-(int(t1) > int(t2)) 
def solution(numbers):
    n = list(map(str,numbers))
    n = sorted(n, key=functools.cmp_to_key(comparator))
    answer = str(int(''.join(n)))
    return answer

 

이 방법은 생각은 했었으나 구현 방법을 몰랐음.

key 값에 lambda 대신 functools의 cmp_to_key를 사용 하여 함수를 통해 구현.

정렬 조건을 내 맘대로 하는것인데 앞으로 보낼걸 1 뒤로 보낼걸 -1 같을 경우 0으로 출력하게 만들어주면 된다.

정렬 문제가 나오면 쓸 수 있을듯

함수 설명: https://docs.python.org/ko/3/library/functools.html