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

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

- 해당 문제를 처음 보고 라이브러리를 활용하여 모든 수의 조합 리스트를 만든 다음 정렬을 진행하고자 했으나,

조합의 시간복잡도 = O(2^n), 순열의 시간복잡도 = O(n!) 이기에 numbers의 길이가 100,000까지 갈 수 있음을 감안하면 시간초과가 발생한다.

- 따라서 다른 방법을 고민해보아야 하는데, 인접한 두 수 끼리 앞 - 뒤, 뒤 - 앞 조합으로 붙여본 후 더 큰 수가 되는 순서대로 정렬하면 된다.

ex) 예를들어 numbers의 두번째 예시 중 [3, 30] 을 비교한다고 했을 때

330 - 303 과 비교하면 330이 크므로, 3이 더 앞에 온다

- 정렬 시 단순 오름차순 / 내림차순이 아닌 사용자가 커스텀하여 정렬 기준을 정하고 싶을 때, cmp_to_key 라이브러리를 활용한다.

 

✅ 풀이

from functools import cmp_to_key

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

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers = sorted(numbers, key = cmp_to_key(compare), reverse=True)
    answer = str(int("".join(numbers)))
    return answer

 

- cmp_to_key의 key가 되는 함수는 return값이 반드시 1, 0, -1 이어야한다. 1은 a와 b를 비교했을 때 a가 앞, -1은 a가 뒤, 0은 순서를 유지하게 된다.

- 예를들어 앞서 언급한 [3, 30]을 비교했을 때 330 > 303 이므로 int(t1) > int(t2)은 1, int(t1) < int(t2) 은 0이 되므로 1 - 0 = 1, 즉 3이 30보다 앞서게 된다.

- 비교 key가 되는 함수를 정의 후에 key = cmp_to_key를 통해 지정하고, 순서를 재배치해 가장 큰 수를 만들어야하므로 reverse=True를 통해 내림차순 정렬한다.

- 마지막 answer에서 한번 정렬한 숫자 문자열을 합친 후에 정수화하는 이유는, numbers의 요소로 0이 포함될 수 있으며 만일의 경우 "00000" 이런 문자열이 만들어진다고 했을 때, 해당 값을 return하는 것이 아니라 "0"을 return 해야하므로 한번 정수화를 통해 0으로 만들어준다.

- 그리고 마지막으로 큰 수를 문자열로 바꾸어 return하므로 문자열로 만들어 return한다.

 

오늘 알게 된 점

- 커스텀한 정렬 기준을 사용하고자 할때, cmp_to_key 라이브러리를 활용하자

- 조합의 시간복잡도는 O(2^n), 순열의 시간복잡도는 O(n!) 이므로 이를 고려하여 문제의 시간복잡도를 계산하자