[Algorithm🧬] 가장 큰 수

문제 / 풀이.py

1. 시간 초과 난 답.

from itertools import permutations

def solution(numbers):
    permu = []
    max = 0
    
    numbers = [str(num) for num in numbers]
    
    permutation = list(permutations(numbers, len(numbers)))
    
    for p in permutation:
        if max < p:
            max = p
    
    return max

이렇게 해보고 직접 조합을 구현해보려고 했는데, 시간 복잡도가 같을 것 같아서 일단 패스.

2. sort

sort 를 이용해야할 것 같아서 sort 를 이용했다.

처음에는

numbers = sorted([str(num for num in numbers], key=lambda x:int(x[0], reverse=True)

을 이용했다. 첫번째 숫자가 크면 먼저 가야하기 때문.

근데 이렇게 정렬을 하면
[3, 30, 34, 5, 9] -> [9, 5, 34, 30, 3] 이렇게 나와버림.. [9, 5, 34, 3, 30] 이렇게 나와야 하는데!!!

test case 1~6 안됨

그래서 30 과 3, 31 과 3, 32 와 3, 33 과 3을 생각해보니, 3을 33 으로 생각하면 비교가 쉽겠다는 생각이 들었음.

세자릿수도 어느 정도 맞아보여서

def priority(s):
    # test case 1 ~ 6 안 된 코드
    s += s[-1] * (4-len(s))
    return s

이걸 sorted 의 key 로 사용했고 실패했다.

그래서 질문하기를 뒤져보니...

[978, 97] -> "97978"
[30, 3021] -> "303021"

과 같은 케이스를 살펴보라고 해서 살펴봤더니... 진짜 제대로 되지 않고 있었다. 그래서 생각해보니, 앞이 일치하는 숫자 두개를 비교할 때는,

978 과 97 이 일치하므로 978의 8과 97의 9를 비교해야함을 깨달았다..
97897 -> 8보다 9가 크니까
97978 -> 3번째 자리에 7가 오는것이 더 큰 수.

거기까지 깨닫고 나서 모르겠어서 다시 질문하기를 뒤져보니 뒤에 그냥 맨 마지막 숫자를 붙이는게 아니라 해당 숫자를 서로 숫자 갯수가 맞게 그대로 붙이면!!

978978 979797

30303030 30213021

이제서야 맞는 비교를 할 수 있어진다. 최대 숫자가 1000 이므로 1자리 2자리 3자리 4자리가 가능하다고 가정하고 12 / len(s) 로 길이를 맞춰주었다. (문자열 비교는 굳이 맞춰주지 않고 3번만 붙여줘도 가능한듯)

test case 11 안됨

그리고 호기롭게 다시 돌렸더니,

[0, 0, 0] -> "0"

을 고려 안했다고 한다...

진짜 진짜 최종 코드

import re

def priority(s):
    # test case 1 ~ 6 안 된 코드
    # s += s[-1] * (4-len(s))
    for i in range(int(12 / len(s)) - 1):
        s += s

    return s
    

def solution(numbers):
    permu = ""
    
    # test case 11 번...
    if re.sub("0", '' ,''.join([str(n) for n in numbers])) == '':
        return "0"
    
    
    numbers = sorted([str(num) for num in numbers], key=lambda x:priority(x), reverse=True)
    
    return "".join(numbers)