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

리스트 순회 모르겠다../

permutations 함수는 시간복잡도가 O(n!) 혹은 O(nr)으로 코딩테스트에 쓰기에는 적합하지 않습니다.

😎 나의 풀이

# 정답은 맞췄지만 시간초과가 뜬다
def solution(numbers):
    from itertools import permutations
    import math
    answer_list = []
    num_list = list(permutations(numbers, len(numbers)))

    for i in range(len(num_list)):
        answer_list.append(''.join(str(x) for x in num_list[i]))
        answer_list.sort(reverse=True)

    return answer_list[0]

• "permutations 함수는 시간복잡도가 $O(n!)$ 혹은 $O(n^r)$으로 코딩테스트에 쓰기에는 적합하지 않습니다."
• permutations 써서 풀었으나 성능테스트에서 다 떨어지고. 경우의수 구하는 알고리즘을 직접 만들어야 하나..하는 생각만 하다가 결국 웹포스팅보고 해결함..

👩🏻‍🏫 다른 풀이

def solution(numbers):
	# int형의 리스트를 map을 사용하여 string으로 치환한 뒤, 리스트로 변환
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x * 3, reverse=True)
    return str(int(''.join(numbers)))

• 정말 대단한 사람 많다
• lambda x : x * 3: num 인자 각각의 문자열을 3번 반복한다는 뜻
• x * 3을 하는 이유?
  num의 인수값이 1000 이하이므로 3자리수로 맞춘 뒤, 비교하겠다는 뜻.
• 문자열 비교는 ASCII 값으로 치환되어 정렬된다.
  따라서 666, 101010, 222의 첫번째 인덱스 값으로 비교한다.
  6 = 86, 1 = 81, 2 = 82 이므로 6 > 2 > 1순으로 크다.
• sort()의 기본 정렬 기준은 오름차순이다. [10, 2, 6]
  reverse = True: 내림차순해주면 [6,2,10]
• 이것을 ‘‘.join(num)을 통해 문자열을 합쳐주면 된다.
• int로 변환한 뒤, 또 str로 변환해주는 이유?
  모든 값이 0일 때(즉, ‘000’을 처리하기 위해) int로 변환한 뒤, 다시 str로 변환한다.

한줄평: I'm...OK.....