정렬 가장 큰 수

프로그래머스 코딩테스트 고득점 Kit 정렬 가장 큰 수

문제 설명

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

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

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

제한사항

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

풀이 포인트

• functools.cmp_to_key를 사용한다.
• 테스트 케이스에 유의

테스트 케이스 추가

numbers(int[])	return
[0, 0, 0, 0]	"0"
[898, 89]	"89898"
[1000, 999]	"9991000"
[333, 334, 3, 33, 4, 35, 30, 55, 31]	"554353343333333130"

solution.py

python3

from functools import cmp_to_key

def sort(a, b):
    if int(a + b) > int(b + a):
        return -1
    else:
        return 1


def solution(numbers):
    answer = ''

    case = list(map(lambda x: str(x), numbers))
    case = sorted(case, key=cmp_to_key(sort))

    if case[0] == '0':
        return '0'

    for i in case:
        answer += i

    return answer

병합 정렬로 구현시

• 통과는 되지만 과정이 복잡하고 functools.cmp_to_key을 사용했을 때보다 느리다.

python3

def merge(array, low, mid, high):
    N = high - low + 1
    temp = [''] * N
    left = low
    right = mid + 1
    bid = 0

    while left <= mid and right <= high:
        if int(array[left] + array[right]) > int(array[right] + array[left]):
            temp[bid] = array[left]
            left += 1
        else:
            temp[bid] = array[right]
            right += 1
        bid += 1

    while left <= mid:
        temp[bid] = array[left]
        bid += 1
        left += 1
    while right <= high:
        temp[bid] = array[right]
        bid += 1
        right += 1

    for i in range(0, N):
        array[low + i] = temp[i]

    return array


def merge_sort(array, low, high):
    if low < high:
        mid = (low + high) // 2
        array = merge_sort(array, low, mid)
        array = merge_sort(array, mid + 1, high)
        array = merge(array, low, mid, high)

    return array


def solution(numbers):
    answer = ''

    case = list(map(lambda x: str(x), numbers))

    merge_sort(case, 0, len(numbers)-1)

    if case[0] == '0':
        return '0'

    for i in case:
        answer += i

    return answer

버블 정렬로 구현시

• 시간 초과

python3

def solution(numbers):
    answer = ''

    test = list(map(lambda x: str(x), numbers))

    test.sort(reverse=True)

    n = 1
    while n > 0:
        if n > 0:
            n = 0
        for i in range(len(test)-1):
            if int(test[i+1] + test[i]) > int(test[i] + test[i+1]):
                test[i], test[i+1] = test[i+1], test[i]
                n += 1

    if test[0] == '0':
        return '0'

    for i in test:
        answer += i

    return answer