[edu] 가장 큰 수 (프로그래머스 lv2)

문제 설명

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, 5, 9]	9534330

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

[설명]

리스트의 모든 요소가 동일 자리 숫자라면 그냥 정렬 해서 다 더하면 된다.

하지만 모두 다른 자릿수를 가지고 있기 때문에 단순 정렬을 사용하면 안된다.

1. 퀵 소트

정렬 하는 방법이 a, b 두 요소를 비교할 때 

자리수가 같으면 a, b 를 비교하고 다르다면 

a+b , b+a 을 비교하면 된다.

2. 문자열 비교

30, 9 둘중 어떤 수를 앞에 위치해야 하나?

9가 더 큰걸로 정의되서 왼쪽에 위치해야한다.

9 와 30 은 9가 일반 문자열 정렬로도 된다. 하지만

3, 30 은 330 이 더 크기 때문에 3이 30 보다 왼쪽에 위치해야 한다

여기서는 "33" 이 "3030" 으로 비교하면 왼쪽부터 비교하기 때문에

3이 더 큰걸로 판별된다.

그럼 "3" * n 에서 n 은 몇번이 되어야 하나?

제일 길이가 긴 요소의 길이 longest 라고 하면

(longest//len(x)+1)

가 되어야 한다.

물론 여기서는 n이 3이라도 상관은 없다.

  

문자열 비교

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

퀵 소트 이용

def max_(a, b):
    return a <= b if len(a) == len(b) else a+b <= b+a


def quick_sort(arr):
    leng = len(arr)
    if leng <= 1:
        return arr
    else:
        pivot = arr[0]
        greater = [element for element in arr[1:] if max_(element, pivot)]
        lesser = [element for element in arr[1:] if not max_(element, pivot)]
        return quick_sort(lesser) + [pivot] + quick_sort(greater)


def solution(nums):
    if set(nums) == {0}:
        return "0"
    nums = [str(num) for num in nums]
    nums = quick_sort(nums)
    return "".join(nums)