42746 가장 큰 수

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

 

# trial 1 -> permutation 사용 (시간 초과)

from itertools import permutations

def solution(numbers):
    perm_lst = list(permutations(numbers))
    max_num = max([int("".join(map(str, perm))) for perm in perm_lst])
    
    return str(max_num)

 

 

# trial 2 -> 문자열 정렬 + 자릿수 차이 보완 (타인 코드 참조)

- (프로그래머스 댓글 인용) 숫자를 반복시키는 이유는 앞에서부터 같은 숫자패턴이 존재하는 숫자들의 비교를 위해서입니다. 기존 숫자를 반복시키게 되면 그 숫자가 앞에 왔을 때 만들 수 있는 최대 숫자를 만들 수 있습니다. (완전한 숫자는 아니구요. 비교가 가능한 범위까지 만들 수있어요)

- [9, 991] 이나 [221,2,10] 의 예시를 생각해보면 쉬움. 9나 2를 3번 반복하지 않으면 99x이나 22x과 적절한 비교가 불가능함. 그리고 이 조건에서 3인 이유는 numbers의 원소가 0이상 1000이하기 때문 (패턴이 세자리까지)

- 약간 앞 패턴이 겹치는 만큼 추가로 반복해줘야하는 느낌? 근데 앞패턴이 최대 2개까지 겹칠 수 있음 (3개 겹치면 사실상 비교 우위가 없어짐 e.g. 9와 999)

- 그리고 자릿수가 적은 것을 좀 더 채워주는 느낌이기 때문에 채우다가 큰 자릿수에 맞춰지면 그 이후로는 비교가 의미없어지는듯

def solution(numbers):
    seq = list(map(str, numbers))
    seq.sort(key=lambda x: x*3, reverse=True)
    
    if sum(numbers) == 0: # 일괄 str(int()) 적용하는 것 보다 더 시간효율적 이라고함
        return "0"
    else:
        return ''.join(seq)

 

 

[개선할 점]

- 이 방법 외에도 모든 숫자 조합을 각각 이어붙어보며 정렬하는 방식도 있음

sorted(n, key=functools.cmp_to_key(comparator), reverse=True)
# return -1: 먼저 들어온 요소가 앞으로 정렬
# return 0 : 바뀌지 않음
# return 1 : 나중에 들어온 요소가 앞으로 정렬