103. 가장 큰 수

문제 설명

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"

풀이 코드(시간 초과): 테스트 케이스 총 15개 중 시간 초과 5개, 실패 1개 / 문제 원소의 길이가 4 이상이면 이 방식 채용

# 차례대로 자릿수를 비교하면서 같거나 작으면 길이가 작은 것부터 와야함 이외에는 내림차순 정렬
# 작은것을 속해있는 것과 동일하게 그대로 크게 늘려 비교
def strange_sort(key, arr):
    ssort = ''
    temp = [] # 각 숫자의 길이 저장
    max_len = 0 # 가장 긴 숫자 길이
    for i in arr:
        temp. append(len(i))
        if max_len < len(i):
            max_len = len(i)

    for i in range(len(arr)):
    # ex) 32와, 3이 있다면 32와 33으로 만듦
        if len(arr[i]) < max_len:
            arr[i] += key
    # 정렬을 각 숫자의 길이가 저장된 배열과 같이 정렬해버림.
    for i in range(len(arr) - 1):
        maxi = i
        for j in range(i + 1, len(arr)):
            if arr[maxi] < arr[j]:
                maxi = j
            # 363, 36 같은 경우 key 값보다 뒤에 있는 값이 크게 나올때, 36 363이 되야함
            if arr[maxi] == arr[j]:
                for k in arr[maxi][1:]:
                    if k > key:
                        maxi = maxi if temp[maxi] < temp[j] else j
                        break
                    elif k < key:
                        maxi = j if temp[maxi] < temp[j] else maxi
                        break
        if maxi != i:
            arr[i], arr[maxi] = arr[maxi], arr[i]
            temp[i], temp[maxi] = temp[maxi], temp[i]





    # 숫자 복원 및 반환할 문자열 만들기
    for i in range(len(arr)):
        arr[i] = arr[i][:temp[i]]
        ssort += arr[i]
    return ssort





def solution(numbers):
    answer = ''
    dic = {
        '9': [],
        '8': [],
        '7': [],
        '6': [],
        '5': [],
        '4': [],
        '3': [],
        '2': [],
        '1': [],
        '0': []
    }
    # 딕셔너리에 추가
    for number in numbers:
        dic[str(number)[0]].append(str(number))

    # 딕셔너리에서 뽑아서 씀.
    for i in range(9,-1,-1):
        # # 내림차순으로 정렬된 value를 차례대로 접근
        # for j in sorted(dic[str(i)], reverse=True):
        #     answer += j
        answer += strange_sort(str(i), dic[str(i)])

    return answer

 

정답 코드:

def solution(numbers):
    answer = ''
    tmp = []
    for number in numbers:
        # 363 36 을 36 363으로, 525 52 를 525 52로 정렬하기 위한 꼼수
        c = (str(number) * 4)[:4] # 4자리수 까지여서 정렬을 위해 이렇게 바꿈(4자리도 1000뿐임)
        length = len(str(number)) # 원래 길이를 복원하기 위해 길이 저장
        tmp.append((c, length))
    tmp.sort(reverse=True)
    for (c, length) in tmp:
        # 다시 length까지 복원해서 답에 붙임
        answer += c[:length]
    # 000을 0으로 바꾸기 위함
    return str(int(answer))