[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 합니다.

입출력 예

numbersreturn

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

---

풀이방법

• (잘못된 방법)
• 처음 접근할 때 순열을 사용하여 모든 경우의 수를 찾은 뒤 가장 큰 수를 문자형으로 바꾸어 출력하도록 만들었다.
• 예시는 통과가 가능했지만 제출 시 모든 테스트에서 시간초과가 발생한다..
• 왜 그럴까?
  • 시간복잡도 O(N!)
  • numbers의 길이는 1이상 100,000이하라는 조건이 있다.  permutations을 사용한다면 당연히 오래 걸릴 수 밖에 없는 방법이었다.

from itertools import permutations

def solution(numbers):
    answer = []
    arr = list(permutations(numbers, len(numbers)))
    for i in arr:
        i = list(map(str, i))
        i = ''.join(i)
        answer.append(int(i))

    answer = list(set(answer))
    answer.sort()
    return str(answer[-1])

ㅠㅠ

---

다른 풀이

• 문제의 핵심은 정렬이다.
• 리스트의 숫자를 int가 아닌 str형으로 정렬하는 경우
  • 예) ['3', '30', '34', '5', '9']는 내림차순으로 ['9', '5', '34', '30', '3']이 될것이다. (문자 한자리씩 ASCII값이 큰 순서대로 정렬함)
  • numbers의 원소는 1000이하 이므로 각 원소의 자리수를 맞추기 위해 *3을 해주면 ['999', '555', '343434', '303030', '333']이 된다
  • 4자리가 넘어가더라도 괜찮다. 뒤에 자리수가 더 있든 없든 문자열을 순서대로 정렬할 것이다.

numbers = [0,0,0,0]

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

print(solution(numbers))