[프로그래머스] 정렬 - 가장 큰 수 (Python)

코딩테스트 연습 - 가장 큰 수

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

 이번 문제의 풀이는 정말 경이롭다. 총 2가지의 실패를 경험하고 다른 분의 코드를 참고했다.

 첫 번째는 str형태는 sort 해줬을 때 앞의 자리 수에 따라 하므로 str로 변환해준 뒤 sort 하고 join으로 합쳐줬다. 이 경우 30이 3보다 크게 나와서 2번째 케이스의 정답이 9534303으로 나오는 악재가 발생.

 그래서 두 번째는 모든 경우의 수를 다루는 permutation을 사용했으나 역시 런타임 에러(시간 초과)가 발생. permutation의 경우 모든 케이스를 다루기 때문에 시간 초과가 안 뜨는걸 거의 보지 못했다. 그래서 어떻게 하면 이것을 줄일 수 있을까 하던 와중 경이로운 풀이를 발견. numbers의 원소가 0 이상 1,000 이하이므로 303이 330보다 작음을 밝히기 위해 x*3을 기준으로 정렬해준다. 그러면 333과 303이 되어 3이 더 큰 것을 밝혀낼 수가 있다.

 다른 풀이로는 시간 복잡도가 O(logN)인 정렬을 구현하는 풀이가 있던데 둘 다 어렵다. 

조건을 확인하고, 그것을 통해 활용할 수 있는 아이디어를 찾는 그 사고를 연습해보자. 결과에 int후 str을 적용하는 경우는 테스트 케이스가 ['0', '0', '0'] 일 때를 위해서이다. 실제로 제한 사항에서도 정답이 너무 클 수 있으니 문자열로 바꾸라는 것으로 보아 000이 아닌 0을 원함을 알 수 있다.