문제 보러 가기 👈 클릭!
💡 풀이
파이썬 알고리즘 인터뷰 61번 가장 큰 수 와 동일한 문제
하지만 프로그래머스에서 동일한 방법(삽입정렬)으로 풀면 시간초과 발생
(삽입 정렬의 시간 복잡도는 O(n2))
✔ 풀이 방법
- numbers의 길이는 1 이상 100,000 이하 이므로 삽입정렬 풀이 방식으로는 시간내에 통과할 수 없다.
- '3'과 '30'은 '330', '3'과 '34'는 '343'으로 합쳐져야 한다.
- numbers의 원소는 0 이상 1,000 이하임에 초점을 맞춰 숫자를 3번 반복하여 3자리수 이상인 수를 만든 후 내림차순 정렬한다.
구현 코드👇
def solution(numbers):
numbers = sorted(list(map(str, numbers)), key = lambda x: x * 3, reverse = True)
return str(int(''.join(numbers)))