[프로그래머스] 가장 큰 수 - 파이썬(python)

 

나의 풀이

def solution(numbers):
    answer = ''
    for i in sorted([str(i) for i in numbers], key=lambda x:x*3, reverse=True) :
        answer += i
    return "0" if answer[0] == '0' else answer

아래와 같은 정렬이 주어졌을 때, 34-> 3 -> 30순으로 정렬이 되어야 한다. 

그렇지만 원래의 문자열 정렬에서는 34 -> 30 -> 3의 순서로 정렬이 되곤 한다.

[3, 30, 34, 5, 9]

"9534330"

 

따라서 numbers의 각 원소들을 문자열로 변경한 후에, key를 x*3 으로 하여 sorted 로 정렬하였다.

x*3을 한 이유는, 343434, 333 , 303030 이 되었을 때는 문자열 정렬이 순서대로 되기 때문이다.

(원소가 1000이하라는 조건에 의하여 3자리 수로 만들기 위해 *3 을 하였음)

 

마지막으로, answer 가 0으로 시작하는 경우에는 "0", "00", "000", ... 와 같은 경우이므로 0을 리턴하도록 하였다.

 

* 문자열 비교연산의 경우엔 첫번째 인덱스를 ascii숫자로 바꿔서 비교한다. 같다면 다음 인덱스도 비교한다. 

 

 

 

다른 풀이

functools 모듈의 cmp_to_key 을 사용한 풀이이다.

functools.cmp_to_key(func) 란?

functools.cmp_to_key(func)
sorted와 같은 정렬 함수의 key 매개변수에 함수(func)를 전달할 때 사용하는 함수이다. 단, func 함수는 두 개의 인수를 받아들이고, 첫번째 인수를 기준으로 그들을 비교하여, 작으면 음수, 같으면 0, 크면 양수를 반환하는 비교 함수이어야 한다.

return 음수 : 먼저 들어온 요소가 앞으로 정렬된다.
return 0 : 바뀌지 않는다.
return 양수 : 나중에 들어온 요소가 앞으로 정렬된다. 

 

import functools

def compare(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(compare),reverse=True)
    answer = str(int(''.join(n)))
    return answer

위 코드에서는 "3", "30" 을 비교할 때, t1="330" t2="303' 이 될 것이다. 따라서 t1이 더 크므로 3이 앞에 정렬된다.

“0000…“ 의 경우, “0”으로 반환될 수 있도록 int 로 형변환을 했다가 (0이 되도록) 다시 str 로 변경한다.

 

* cmp_to_key 를 이용해서 자신만의 비교 함수를 만들어서 사용한다면 sorting 에서 유리할 것이다!

 

 

from itertools import permutations

def solution(num):
    permute = list(permutations(num,len(num)))
    list_permute = [str(i) for i in permute]   
    answer = max(list_permute)
    
    return answer

순열을 구해주는 permuations 를 사용한 풀이인데, 이 방법은 테스트케이스는 모두 통과하나 시간 초과가 된다.

그도 그럴것이 순열에 대한 모든 경우의수를 구하고, 가장 큰 원소를 찾는 max 함수까지 사용하기 때문이다.

 

틀린 풀이이지만, permutations 를 사용하는 방법을 처음 알게 되어 가져와보았다.