[프로그래머스] 가장 큰 수

문제 설명

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

 

[python]

def solution(numbers):
    number_list = [str(num) for num in numbers]
    for i in range(1, len(numbers)) :
        for j in range(1, len(numbers)) :
            if int(number_list[j-1]+number_list[j]) < int(number_list[j]+number_list[j-1]) :
                number_list[j], number_list[j-1] = number_list[j-1], number_list[j]
    return str(int(''.join(number_list)))

 

처음으로 도전한 코드다.. 버블 정렬을 이용해서 하려고 했으나.. 시간 초과로 실패했다..

 

def check(n1: str, n2: str) -> bool :
    return n1+n2 < n2+n1

def solution(numbers):
    num_list = [str(num) for num in numbers]
    i = 1
    while i < len(numbers) :
        idx = i
        while idx > 0 and check(num_list[idx-1], num_list[idx]) :
            num_list[idx-1], num_list[idx] = num_list[idx], num_list[idx-1]
            idx -= 1
        i+=1
        
    return str(int(''.join(num_list)))

 

이번에는 삽입정렬로 해보았다.. 우씨 이것도 시간 초과다.. check함수는 너무 지저분해 보여서 함수로 변경했다.

 

def check(n1: str, n2: str) -> bool :
    return n1+n2 < n2+n1

def solution(numbers):
    num_list = [str(num) for num in numbers]
    num_list.sort(reverse=True)
    i = 1
    while i < len(numbers) :
        idx = i
        while idx > 0 and check(num_list[idx-1], num_list[idx]) :
            num_list[idx-1], num_list[idx] = num_list[idx], num_list[idx-1]
            idx -= 1
        i+=1
        
    return str(int(''.join(num_list)))

 

이다음으로 도전한 코드다.. 우씨.. num_list.sort(reverse=True)를 추가했다.

 

삽입 정렬은 최악의 상황의 경우에는 O(n^2)까지 올라가기 때문에 삽입 정렬 전에 정렬을 한번 해주었다..

 

으.. 오늘 아침부터 붙잡고있었는데 너무 오래 걸렸다..