Step 3. 정렬(Sort) 대표 문제 풀이: 가장 큰 수

---

문제분석

반복문을 이용한 풀이

1. 빈 문자열로 수를 초기화 한다
2. 가장 크게 만들 수 있는 수를 고른다
3. 그 수를 현재 수에 이어 붙인다
4. 모든 수를 다 사용할 때까지 반복한다.

해당 문제의 시간 복잡도 : O(N^2)

Sort 를 이용한 풀이

1. 빈 문자열로 수를 초기화 한다.
2. 수의 목록을 (크게 만드는 것 우선으로) 정렬한다.
3. 목록에서 하나씩 꺼내어 현재 수에 이어 붙인다.
4. 모든 수를 다 사용할 때까지 반복한다.

해당 문제의 시간 복잡도 : O(NlogN)

크게 만드는 수의 기준

• 예를 들어 34의 경우
  결과의 수를 가장 크게 만드는 것 우선으로 정렬이 다 되어 있다고 가정하면,
  34보다 뒤에 올 수 있는 것은 커봐야 34를 넘지 못한다.
• 그렇기 때문에 주어진 수를 쭉 이어붙이며,
  문제에서 주어진 목록에서 들어있는 수는 1000 이하라고 했으므로 4글자에서 끊어 비교한다.

---

알고리즘

알고리즘 설계 -> 구현

1. 대소 관계 비교를 위한 기준을 마련
2. 이것을 이용하여 주어진 배열을 정렬
3. 정렬된 배열을 이용하여 문자열 표현을 완성

코드

def solution(numbers):
    numbers = [str(x) for x in numbers]
    numbers.sort(key = lambda x : (x*4)[:4], reverse = True)
    if numbers[0] == '0':
        answer = '0'
    else:
        answer = ''.join(numbers)
    return answer

시간복잡도

numbers의 원소를 itos 변환 -> O(N)
numbers 리스트를 정렬 -> O(NlogN)
numbres 리스트를 join -> O(N)

전체 알고리즘 : O(NlogN)

---