[ Programmers 42746 ] 가장 큰 수(Python)

uoayop·2021년 5월 7일
0

알고리즘 문제

목록 보기
36/103
post-thumbnail

문제

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

주어진 정수들을 조합해 가장 큰 수를 만드는 문제다.
지금 레벨 2만 조지고 있는데,, 내가 조져지고 있다. 아뿔싸ㅜ


문제 풀이

[틀린 풀이]
람다를 이용해서 숫자의 첫번째 자릿수를 비교해주면 되겠다고 생각했다.
그럼 9, 8, 7, 12 ... 이렇게 정리될 거라고 생각했다.
원하는 결과는 나왔지만 오답이었다.

numbers = list(map(str, numbers))
    numbers = (sorted(numbers, key=lambda x: x[0], reverse=True))

[예외]
20, 203 같은 경우 20320이 정답이지만 20203이 나왔다.
첫번째 자리만 비교했기때문에 이와 같은 결과가 나왔다.


[틀린 풀이 2]
그럼 마지막 자리도 비교해주면 되지 않을까? 라고,, 생각했다 ㅋㅎ.,,
위의 예외는 해결되지만 당연히 틀리다.

[예외]
4223, 4991 같은 경우 첫번째 자리, 마지막 자리는 비교가 되지만 가운데 자리가 비교가 되지 않아서 오답이 나온다.


[정답 풀이]
그래서 한참 고민을 하다가 풀이를 찾아보았다.
유림님 블로그에서 숫자가 아닌 문자열첫번째 자리로 비교로 한 뒤, 문자의 길이로 비교를 한다는 사실을 알게되었다.

  1. 6, 13, 3, 1 이라는 숫자에 대해서 각 문자를 임의로 5번씩 곱해준 값을 key로 두고 정렬을 해줄 것이다.
    66666, 1313131313, 33333, 11111
  2. 위와 같이 곱해진 문자열이 정렬되는 기준은
    (첫번째 자리 비교) 👉🏻 (문자열의 길이) 이다.
  3. 따라서 66666, 33333, 1313131313, 11111 순으로 정렬이 될 것이다.

코드

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))
    numbers = (sorted(numbers, key=lambda x: x * 5, reverse=True))

    for n in numbers:
        answer += str(n)
    return str(int(answer))
profile
slow and steady wins the race 🐢

0개의 댓글