[프로그래머스/Python] 가장 큰 수

문제

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.

• numbers의 원소는 0 이상 1,000 이하입니다.

• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

풀이

접근 방식

처음에는 단순히 숫자들을 문자열로 바꿔서 내림차순 정렬을 해주었는데, 예제 2번의 경우가 들어맞지 않았다. 예제 2번의 경우 보면, [3, 30, 34]로 큰 수를 만드려면 [34, 3, 30]으로 정렬되어야 큰 수가 만들어진다. 나처럼 단순히 내림차순 정렬을 하면 [34, 30, 3]으로 정렬되어서 틀린 답이 된다. 이 부분을 해결을 못해서 다른 사람들 접근 방식을 찾아보며 힌트를 얻었다.

풀이는 아래 링크를 참고하여 다시 풀어보았다.
https://esoongan.tistory.com/103

문제 조건에서 각 원소의 길이는 1,000 이하이기 때문에 문자열 길이를 3배로 늘린 후에 비교하는 방식으로 풀이를 진행했다. 숫자 비교연산과 달리, 문자열 비교연산은 첫번째 인덱스를 아스키 숫자로 바꿔서 비교하고, 같으면 그 다음 인덱스를 비교한다. 예를 들어 [3, 31, 310] 이라는 리스트가 있다고 해보자. 이를 문자열 비교연산을 진행하면 아래와 같다.

• 3 ----> 3 3 3

• 31 ---> 3 1 3 1 3 1

• 310 --> 3 1 0 3 1 0 3 1 0

위와 같이 각 문자열을 3배로 늘려서 각 자리를 비교했을 때, [3, 31, 310] 순서로 정렬할 수 있다.

추가로 [0, 0, 0, 0]과 같은 케이스는 0으로 반환되어야 한다. 그러기 위해서 문자열로 합친 0000을 정수형으로 변환시켜야 0이 된다.

def solution(numbers):
    answer = ''
    nums = list(map(str, numbers))
    
    nums.sort(key=lambda x: x*3, reverse=True)
    answer = str(int(''.join(nums)))
    return answer