[Python][정렬] 프로그래머스 - 가장 큰 수(Level2)

문제출처 - https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수 | 프로그래머스

틀린 풀이 1

from itertools import permutations


def solution(numbers):
    answer = ''
    permutation_list = permutations(numbers)
    max_number = 0

    for i in permutation_list:
        temp = int(''.join(map(str, i)))

        if max_number < temp:
            max_number = temp

    answer = str(max_number)
    return answer

처음엔 numbers 리스트의 모든 순열을 구하고 그 중 가장 큰 값을 찾았다.

하지만 테스트케이스 모두 시간초과...

(permutation의 시간복잡도는 얼마인지 잘 모르겠다 아마 버블정렬보다 크니까 전부 시간초과 뜨겠지..? 아시는 분 있으면 알려주세요ㅠㅠ)

 

 

틀린 풀이 2

def solution(numbers):
    answer = ''

    numbers = list(map(str, numbers))  # str 리스트로 바꿔주기
    max_numbers = []

    while len(numbers) != 0:
        max_numbers.append(max(numbers))
        numbers.remove(max(numbers))

    return answer

numbers 리스트를 모두 str형으로 바꿔주고 그중 max값을 하나씩 뽑으면서 정답에 추가해줬다.

그랬더니 테스트케이스2에서 [3, 30, 34]가 [34, 30, 3]으로 정렬이 되어 실패...

 

 

틀린 풀이 3

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))  # str 리스트로 바꿔주기

    for i in range(0, len(numbers) - 1):
        for j in range(i + 1, len(numbers)):
            if int(numbers[i] + numbers[j]) < int(numbers[j] + numbers[i]):
                numbers[i], numbers[j] = numbers[j], numbers[i]

    answer = ''.join(numbers)
    return answer

버블 정렬을 이용해서 풀었다.

이건 그래도 반은 맞았는데 반은 시간초과...

버블정렬의 시간복잡도는 O(N^2)

 

 

맞는 풀이

def mergeSort(x):
    if len(x) > 1:
        mid = len(x)//2
        lx, rx = x[:mid], x[mid:]
        mergeSort(lx)
        mergeSort(rx)

        li, ri, i = 0, 0, 0
        while li < len(lx) and ri < len(rx):
            if int(lx[li]+rx[ri]) > int(rx[ri]+lx[li]):
                x[i] = lx[li]
                li += 1
            else:
                x[i] = rx[ri]
                ri += 1
            i += 1
        x[i:] = lx[li:] if li != len(lx) else rx[ri:]
        

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))  # str 리스트로 바꿔주기
    
    mergeSort(numbers)
                
    answer = ''.join(numbers)
    
    if int(answer) == 0: answer = '0'  # 이거 추가 안하면 테스트11번 실패뜸
    
    return answer

드디어 성공했다.

이번엔 병합정렬을 사용해봤다. 병합정렬은 시간복잡도가 O(logN)

이번에도 numbers 리스트 원소를 모두 str형으로 바꾸고 int(a+b)랑 int(b+a)를 비교해서 큰값부터 하나하나 정렬되게 구현했다.

 

 

다른사람 풀이

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

분석

numbers.sort(key=lambda x: x*3, reverse=True)
numbers.sort(key=lambda x: (x[0], x[1%len(x)], x[2%len(x)], x[3%len(x)]), reverse=True)

위의 두 코드가 같은 의미인 것 같다...

 

이 문제에서 포인트는 

 

"numbers의 원소는 0 이상 1,000 이하입니다."라고 제한사항에 적혀있는데

 

그러면 numbers의 각 원소들을 4자리까지만 비교해주면 된다.

 

만약에 숫자가 '12'인 경우는 2자리밖에 없기 때문에 나머지 자리수는 나머지 연산을 통해 가져온다.

 

예를 들어, 숫자가 '12'이면

 

x[0] = 1

x[1] = 2

x[2%len(x)] = x[0] = 1

x[3%len(x)] = x[1] = 2

 

해서 '12'는 결과적으로 '1212'인 문자열이 된다.

 

 

❗ return할때 int형으로 먼저 바꿔주고 return하지 않으면 테스트케이스 11번에서 실패뜸

   만약 ['0', '0', '0']인 경우 int형으로 바꿔주지 않고 str(''.join(numbers))를 하게 되면 '000'이 리턴되기 때문이다.