파이썬(Python) 알고리즘 문제풀이 가장 큰 수[프로그래머스 / 정렬]

출처) 프로그래머스 Facebook

문제 설명

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

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

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

 

 

제한사항

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

 

 

입출력 예시

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 59]	"9534330"

 

 

풀이 코드

처음에 permutations 를 생각했는데, (순서가 중요하니까) numbers 길이가 최대 10만이기 때문에 최악의 경우 100,000 P 100,000 만큼의 경우의 수가 나온다. 즉 100,000! 이기 때문에 무대뽀로 풀면 무조건 시간 초과가 발생..
테스트케이스 2번을 축소시켜서 [3, 30, 34] 라고 가정했을 때 일반적인 정렬로는 우리가 원하는 값인 "34330" 이 아닌 "34303" 이라는 값이 나오기 때문에 어떤 기준으로 문자열을 붙여야하나 많은 고민을 했고 functools 의 cmp_to_key() 를 활용해 풀이했다.
numbers 의 원소는 0 이상이라고 했으니까 numbers = [0, 0, 0, 0 ...] 이런 경우 '0' 을 반환한다는 예외를 꼭 잡아줘야한다. 처음에 안잡아줘서 틀렸음 ..

 

1. numbers 리스트를 문자열로 비교하기 위해 문자열 리스트로 초기화한다.

2. x(앞 원소) + y(뒤 원소) 와 y(뒤 원소) + x(앞 원소) 를 문자열 합치기를 통해 합치고 숫자로 변경해 어느 것이 더 큰지 확인하고 내림차순한다.

3. 정렬된 리스트를 join() 메서드를 통해 모두 합친 후 결과 문자열을 반환한다.

def solution(numbers):
    if sum(numbers) == 0:
        reutnr '0'

    numbers = [str(num) for num in numbers]

    numbers.sort(key=cmp_to_key(lambda x, y: int(x + y) - int(y + x)), reverse=True)

    return ''.join(numbers)