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

코딩테스트 연습 - 가장 큰 수

 

 

 

[내 풀이]

def solution(numbers):
    from itertools import permutations as pmt
    
    temp = list(pmt(numbers, len(numbers)))
    li = ["".join(map(str,i)) for i in temp]
    return max(li)

완전 탐색.

permutation의 조합툴을 활용해 모든 경우의 수를 리스트에 담아주고, 그 중 가장 큰 수를 반환해냈다.

당연히 그렇겠지만 시간 초과.

 

정확도에서는 맞지만 효율성에서 시간초과가 뜬다는 말은

내 방법으로 풀 수는 있지만 더 좋은 다른 방법이 있다는 뜻.

더 효율적으로 문제를 푸는 다른 알고리즘을 생각해내자.

 

조인함수는 인자로 리스트, 튜플 받아도 되고,

map함수를 받아도 괜찮은 것 같다.

 

[타 풀이 1]

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

미친 풀이인거 같다.

특히 x*3으로 반복수를 비교해주는 부분이 나는 절대 못떠올렸을만한...

 

 

[str(x) for x in numbers]

반복문으로 str 거는것보다

list(map(str, numbers))

이렇게 map으로 만드는 것이 더 빠르다!

 

 

[타 풀이 2]

import functools
 
#  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0
def comparator(a,b):
    t1, t2 = a+b, b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) 
 
def solution(numbers):
    n = list(map(str, numbers))
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

 

리스트는 sort / sorted 함수로 정렬할 수 있다.

정렬하는 기준을 key 파라미터로 줄 수 있는데, 

[타 풀이1] 처럼 함수가 간단하다면 lambda를 쓰고

아니면 위와 같이 comaprator와 같은 비교함수를 구현한 뒤 functools.cmp_to_key로 연결해주면 된다.

 

functools.cmp_to_key(func) 함수는 sorted와 같은 정렬 함수의 key 매개변수에 함수(func)를 전달할 때 사용하는 함수이다.

단, func 함수는 두 개의 인수를 받아들이고,

첫번째 인수를 기준으로 그들을 비교하여, 작으면 음수, 같으면 0, 크면 양수를 반환하는 비교 함수이어야 한다.