정렬_가장 큰 수_python

문제 설명

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 원소는 1000이하라는 점을 이용하였다.

배열을 [6666, 1010, 2222] 처럼 자릿수를 1000자릿수로 맞혀주고 이를 내림차순 정렬을 한 후 앞에서부터 문자열 값을 하나씩 더했을때가 가장 큰 값이 나오는 경우이다.

그럼에도 원하는 배열을 만들었으나 배열을 만들기 전의 원소 값으로 answer 값에 더해줘야하는데

이 방법으로는 해결 하지 못했다. 

def solution(numbers):
    answer = ''
    # numbers의 원소인 1000이하 숫자 비교를 위해 모두 4자리를 만족시켜준다.
    box = []
    
    
    for number in numbers:
        if 10 <= number < 100:
            str_number = str(number) * 2
        elif 100 <= number <1000:
            str_numbere = str(number) + "0"
        else:
            str_number = str(number) * 4
        
        box.append(str_number)
    
    print(sorted(box, reverse=True))
    # ['9999', '5555', '3434', '3333', '3030']
    
    return answer

---

sort, sorted의 key, reverse

sort, sorted는 key와 reverse 를 매개변수로 갖는데, key에는 정렬을 목적으로 하는 함수를 값으로 넣어 특정 기준으로 정렬을 할 수 있다. 

key 인자에 함수를 넘겨주면 해당 함수의 반환값을 비교하며 순서대로 정렬한다.

결론은 sort를 key 값에 lambad 함수를 적용하여 문자열을 정렬하는 방법으로 해결하였다.

대표적인 해당 문제를 푸는 방법으로 알려져있는 방법이다.(아직 한참 멀었다고 생각한다ㅠㅠ)

---

key에는 람다 함수를 값으로 넣어 실제로는 6, 10, 2를 기준으로 정렬을 하는 것이 아닌

x*4 ==> 6666, 10101010, 2222를 적용한 기준으로 정렬을 한다.

따라서, 각 문자열 인덱스의 앞자리인 6, 2, 1을 정렬하며

만약 인덱스 앞자리가 동일할 경우 바로 뒤인덱스까지 비교하는 점을 이용한다.

numbers1 = [3, 30, 34, 5, 9]
box = list(map(str, numbers1))
print(box)
# ['3', '30', '34', '5', '9']
box.sort(key=lambda x: x*4, reverse=True)
# '3333', '30303030', '34343434', '5555', '9999' 를 비교
print(box)
# ['9', '5', '34', '3', '30']

def solution(numbers):
    answer = ''
    # numbers의 원소인 1000이하 숫자 비교를 위해 모두 4자리를 만족시켜준다.
    box = list(map(str, numbers))
    print(box)
    # ['6', '10', '2']
    box.sort(key=lambda x: x*4, reverse=True)
    print(box)
    # ['6', '2', '10']
    answer = str(int(''.join(box))))
    
    return answer

---

시간복잡도

리스트 맵핑 => O(N)

파이썬 정렬 알고리즘 => O(NlogN)

리스트 조인 => O(N) 리스트의 요소만큼

총 시간 복잡도는 O(NlogN) 으로 생각한다

sort에 key 매개변수에 함수를 넣는 방법으로 정렬할 수 있는 점을 꼭 기억해야겠다.