programmers - 가장 큰 수

풀이

문자열 정렬의 아이디어는 항상 갖고 있는게 좋을 것 같다. 약간 스킬 적인 측면으로 작용하는데(~~~이거 버그아닌데 스끼린데~~~) 음 일단 보자.

이 문제는 보면 특징이 있다. 일단 다 만드는 것은 잘못된 방법이다. 순열의 개수가 너무 많이 나와서 시간 복잡도가 팩토리얼로 증가한다. 그러면 어떤 방법이 있을 텐데, 결국 규칙을 찾아야만 한다. 이 규칙은 차근차근 해보면 분석할 수 있다. 푸는 방법이 문제일 뿐.

일단 앞자리가 크면 좋다. 근데 그러면서 값이 크면 되냐? 그건 아니다. 3, 30을 비교해보면 330이더 커서 3이 더커야 한다는 결론이 나온다. 그러면 결국 3이 0과 비교했을 때 크기 때문에 더 커야 한다는 결론이 나온다. 그래서 이를 comp 로 정의해서 커스텀 정렬을 하려했으나 로직이 너무 복잡해서 다른 방법을 생각했다. 그럼 위의 생각에서 이렇게 생각해도 무방할지 테스트를 해봤다. 33, 30 이러면 33이 더 크다. 0과 3이 같은 자리에서 비교가 되니까. 그럼 41, 430은? 414 430. 430이 더 크다는 결론이 나오고 실제 값도 430414가 414430보다 더 크다. 이게 좋은 방향인 것 같다. 그러면 어디까지 늘려서 반영해야 할까. 일단 4자리니까 그 이상으로 먹여서 정렬을 하게 하면 좋을 것 같다. 그래서 아래의 풀이가 나오게 되었다. 마지막에 꼭 int로 변환하고 다시 str로 변환하자. 이게 숫자로 값을 비교하라고 한 것이라서 0, 0, 0, 0 이런시긍로 들어오면 답이 0000이 되어버린다. 주의할 것. 항상 0은 숫자연산할 때 고민을 할 대상이다.

Code

def solution(numbers):
    # 다 만드는 건 미친 짓. 
    # 방법이 있을 것
    # 일단 첫번째, 앞자리가 크면 좋다.
    # 길이가 길다고 해서 좋은 것이 아니다.
    # 3 30 이면 330 303이라서 다르다.
    # 즉 뒤에 숫자가 현재 비교하고 있는 앞 숫자보다 작으면 얘는 기각
    # 3 -> 33 30 이런식으로 만들어서 비교하면 어떨까
    # 그럼 그 뒤의 숫자가 반영됨
    # 41 430
    # 4141 430430
    # 41430 43041
    # 처음 앞 숫자의 크기를 뒤까지 반영해 주기 위해 얘를 억지로 늘려줘야 한다. 어디까지?
    # 4444 45
    # 4444 4545
    # 생각하기 싫다 5자리로 해서 비교하자.
    numbers = list(map(str, numbers))
    numbers = sorted(numbers, key=lambda x: (x*5)[:5], reverse=True)
    answer = str(int("".join(numbers))) # 숫자니까 만약에 0000이렇게되면 답 틀린다.
    return answer