[알고리즘] 프로그래머스 가장 큰 수(LV2)

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

프로그래머스

 

오늘은 간단하게 정렬카테고리에 있는 가장 큰 수를 만드는 문제를 풀어보았다. 다음 그림과 같이 주어진 배열의 수를 사용해 만들 수 있는 가장 큰 수를 리턴하는 문제이다.

위의 배열을 보면 34, 3, 30 순으로 정렬이 되어야 하는데 문자열로 변환해서 정렬해 보니 [9, 5, 34, 30, 3] 순으로 정렬이 되었다. 그럼 어떻게 정렬을 해야 34, 3, 30 순으로 정렬이 될까?

 

나는 간단하게 생각해서 자리 수를 마지막자리를 반복하여 채워 넣어 비교하는 방식으로 해보기로 했다.

def solution(numbers):
    answer = ''
    string_numbers = list(map(str, numbers))
    max_length = len(str(max(numbers)))
    
    for i in range(len(string_numbers)):
        string = string_numbers[i]
        length = len(string)
        if length < max_length:
            padding = max_length - length
            string_numbers[i] = string + string[-1] * padding
    zip_list = zip(string_numbers, numbers)
    string_numbers, origin = zip(*sorted(zip_list, reverse=True))
    answer = "".join(map(str, origin))
    return answer

 

원본 배열과 정렬을 위해 만든 배열을 zip으로 묶어 정렬을 해주었는데 잘 나온 것 같다.

그래서 코드를 완성해서 제출했는데 뭔가 꺼림칙했는데 바로 틀려버렸다. ㅎㅎ

 

테스트케이스는 통과하는데 예외케이스[40, 404, 405] 가 있었다. ㅎㅎㅎ

 

문자열을 두고 x+y > y+x를 비교하는식으로 버블정렬로 구현했지만 한문제를 제외하고 시간초과여서 아이디어 그대로 퀵정렬을 사용하여 해결했다. 테스트 케이스 11번 때문에 좀 오래걸렸는데 이건 [0,0,0] 일때를 처리해줘서 해결했다.

// 버블정렬
def solution(numbers):
    answer = ''
    string_numbers = list(map(str, numbers))
    length = len(string_numbers)
    
    for i in range(length-1):
        for j in range(length-i-1):
            x = string_numbers[j]
            y = string_numbers[j+1]
            if x+y < y+x:
                string_numbers[j] = y
                string_numbers[j + 1] = x

                
    answer = "".join(map(str, string_numbers))
    return answer

def quick_sort(numbers):
    if len(numbers) <= 1:
        return numbers

    pivot = numbers[0]
    left = [x for x in numbers[1:] if x + pivot >= pivot + x]
    right = [x for x in numbers[1:] if x + pivot < pivot + x]

    return quick_sort(left) + [pivot] + quick_sort(right)

def solution(numbers):
    string_numbers = list(map(str, numbers))
    
    sorted_numbers = quick_sort(string_numbers)
                
    answer = "".join(sorted_numbers)
    
    return "0" if answer[0] == "0" else answer