[ 프로그래머스 ] 정렬 > 가장 큰 수 파이썬python 풀이

프로그래머스 문제는

풀기만 하고 정리를 안해서

아직 깃헙에도 못 올리고 있는데

이 문제는 쓰임이 많을것 같아

기억을 위해 정리를 해 두고

넘어가고자 한다.

 

 

// 문제요약

 

0 또는 양의 정수가 주어졌을때,

정수들을 이어서 만들 수 있는

가장 큰 정수를 구해라.

 

// 풀이

 

굉장히 쉬워보여서 금방 끝낼 줄 알았지만

완벽히 이해하는데 시간을 많이 들인

의외의 문제다.

 

 

코드를 먼저 보자.

def solution(numbers):
    def sort_key(x: str) -> str:
        return (x*4)[:4]
        
    numbers = sorted([str(n) for n in numbers],
                     reverse = True,
                     key = sort_key)
    return str(int(''.join(numbers)))

 내가 시도한 무수한 방법들은 모두 허사였다.

 

나도 자릿수를 맞추는데까지는 생각이 갔으나

0 혹은 9를 이용해서

left padding 혹은 right padding

하는 정도로만 생각했다.

 

그러다가 풀이들을 봤는데

그냥 숫자를 여러번 반복하면

풀린다는 다소 어처구니없는 방법들로

다들 잘 풀어냈다는 것을 보았다.

 

이건 사실 풀이 방법을 외워버릴 수도 있지만

내 천성이 허락하지 않아서

이해가 완벽히 될때까지 후벼파 보았다.

 

 

1. 자릿수가 같은 경우

pass

 

2. 자릿수가 다른 경우

가장 간단한 케이스부터 생각하면 쉽다.

주어진 두 수를

A

BC

라고 하자.

 

그리고 4자리 수를 채워주기 위해서 반복하면

AAAA

BCBC

가 된다. 여기서 왜? 라는 생각이 떠나지 않았다.

이게 왜 된다는거지? 된다는건 알겠는데 왜?

그래서 차근 차근 보면

 

 

문자열 sorting은 맨 앞자리수부터

하나의 문자씩 고려하여 비교한다.

 

자 그러면 index에 따라 보도록 하자.

0 )

A와 B 모두 두 수중 가장 앞자리의 숫자다.

따라서 뭐든 큰쪽이 맨 앞으로 가면

완성된 수의 가장 큰 자리가 가장 큰 숫자가 된다.

그런데 이 둘이 같다면 문제가 생긴다.

어떤 수를 앞으로 내던지

완성된 수의 가장 큰 자리가 같아지기 때문이다.

그래서 다음 인덱스를 비교해야 한다.

 

1 )

A와 C가 주어졌다.

만약 A가 맨 앞으로 가는 경우

완성된 수는 ABC 가 된다.

그러면 이런 의문이 들 수 있다.

 

A = B 니까 결국 AAC 이므로

ACA 가 AAC 보다 클 수 있을까?

 

무슨 말인고 하니 A와 B 가 같다면

어차피 두번째 자리의 수는

A혹은 B보다 같거나 커야만 한다.

그러니까 이 비교를 위해서

A, B와 같은 값이 한번 더 오는 것일뿐

의미없이 수를 반복한다고 이해하면

머릿속이 뿌옇게된다.

 

 

이런식으로

1. 큰 수면 무조건 먼저 나가라

2. 둘이 같으면 다음에 올 자리수가

    그 수보다 크냐? ㅇㅋ 그러면 먼저 나가라

의 규칙에 맞춰서 비교를 하면

결국 완성된 수는 무조건 가장 크다.

 

이 비교를 수행하는 방법은 수를 반복하여

하나의 문자열을 만드는 것이고

문제에서 1000이하의 수만 주어진다고 했으므로

최대 4자리까지 반복해주면 된다.

 

그리고 sort를 하면 min -> max 순으로 정렬이므로

뒤집어주기위해서 reverse = True를 해준다.