[프로그래머스] 가장 큰 수 - 파이썬

January 21, 2021

문제 설명

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

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

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

제한 사항

numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

내 코드

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

진짜 쉬운 문제인 줄 알았다. 근데 해당 문제를 sort()하는 것 까지는 생각했는데, numbers.sort(key = lambda x : (int(x[0]), int(x[-1])), reverse = True)와 같은 식으로 다중 조건을 넣은 필터로 해봤는데, 꼭 걸리는 테스트 케이스들이 있었다. 예를 들면 [5,9,3,34,30]이나 [403,40]과 같은 데이터가 들어오면 어떤 다중 조건을 넣어봐도 양쪽을 만족 시킬 수 없었다. 결국 이번 문제는 너무 시간이 많이 걸리는 것 같아서, 해당 문제 푼 것을 찾아보았는데 x*3과 같은 조건은 생각지도 못한 조건이었다. 이 조건을 통해서 자리수를 맞춰서 비교할 수 있고 숫자문자열끼리 크기를 비교하게되면 첫 번째 숫자의 ASCII 코드 값을 비교하게 된다. 만약 첫번째 ASCII코드가 같다면 그 뒤를 비교하기 때문에 원하는 결과를 얻게 정렬 할 수 있다. 예를 들어 [403,40]과 같은 경우에 x*3을 적용하면 [403403403,404040]을 비교하게 되고, 40까지는 같지만 403,404까지 보면 3과 4를 비교했을 때 아스키코드 값이 4가 더 크기 때문에 더 앞서게 되서 결국 [40,403]으로 정렬된다. 그리고 마지막 정답 출력 부분에 str()과 int()를 더 쓴 이유는 정렬하여 문자열로 붙인 결과가 000000과 같다면 가장 큰 수가 0이 나와야하기 때문에 int()를 한번 씌우고 나면 0이 되고, 그걸 다시 문자로 바꿔야해서 str()을 쓴 것이다. 발상의 전환이 필요한 것을 절실히 느꼈다. 많이 풀다보면 노련함이 생기지 않을까…하는 생각을 해본다.

다른 사람의 코드

import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

comparator()라는 함수를 만들어서 사용했는데, 해당 함수는 문자열 a와 b를 받아서 문자열을 이어보고 int()로 변환하여 둘 중 어떤 인자가 먼저 일지를 반환하였다. 그 과정에서 비교 함수를 사용하기 위해서 functools 모듈의 cmp_to_key()함수를 사용하였다. 이 방법이 정석일 수도 있으나, 아직 나에게는 lambda를 쓰는 것이 더 익숙하고 괜찮게 느껴진다.