정렬 2-가장큰수 찾기

프로그래머스 가장 큰 수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42746

우선 브루트포스 방식으로 numbers의 수 permutations를 모두 찾아
순서대로 sort하면 최댓값을 찾을 수 있을 것 같아 그렇게 풀었다.
하지만 시간초과가 난다.

from itertools import permutations

def solution(numbers):
    answer = ''
    candidates=[0]

    for num in permutations(numbers,len(numbers)):
        num_candi=int(''.join(map(str,num)))
        if candidates[-1]< num_candi:
            candidates[-1]=num_candi
    

    answer=str(candidates[-1])
    return answer

결국 numbers의 permutation을 구하는 만큼의 시간복잡도보다 빨라야 한다는 것인데, 역시 정렬의 과정에 개입할 수 밖에 없겠다고 생각했다.
그래서 생각해본 방법은 탐욕 알고리즘과 비슷하게 큰수부터 앞에 오도록 취하는 방법이었다. 하지만 그럴경우 자리수가 더 크고 앞자리수 하나만 비교하면 작은 수가 앞에오면 정답이 되지 않는다.

나입 답

def solution(numbers):
    answer = ''
    numbers=list(map(str,numbers))

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

    return answer

• 느낀 점

• 작은 수를 포함하는 것이 뒤에 가야 한다는 것을 알아채지 못했다.
  알았어도 한자리수를 이어붙여 자릿수를 채워 비교할 생각을 못했다.
  sort의 key에 대해 몰라서 구현을 못했을 것 같다.
  숫자0-9가 아스키 코드의 80-89에 저장된다는 것을 알았다면 더 생각할 거리가 있었을 것같다.

• lamda표현식에 대해 무지했다.

• 문자열을 sort할 경우 어떻게 정렬해 반환하는지 전혀 몰랐다.
  문자의 경우 대문자 알파벳순>소문자 알파벳 순으로 정렬된다.

• join은 하고 int캐스팅을 하고 다시 str캐스팅을 함으로써 0000,0009 같은 수가 0,9로 번역되야 한다는 것도 몰랐다.

• 우선 작은 숫자를 가진 수가 뒤에 위치해야 한다는 것을 알아챈후, 이를 구현할 방법으로 한자리 숫자라도 복사해 자릿수를 늘려서 비교할 생각을 해내서 sort의key로 주어 정렬 해냈어야 한다.

https://dojang.io/mod/page/view.php?id=2360

sort 정리-key,reverse

sorted( <list> , key = <function> , reverse = <bool>)
# <list> 뿐 아니라, <Tuple>, <Dictionary>, <Str>에도 사용 가능하다.

key를 통해 정렬기준을 정할 수 있다.
reverse=r=True 이면 내림차순,False이면 오름차순으로 정렬한다.

array = [[50, "apple"], [30, "banana"] , [400, "melon"]]
위와 같은 array가 있으면

array.sort(key = lambda x:x[0])
print(array)
>>>>> [[30, 'banana'], [50, 'apple'], [400, 'melon']]

이렇게 key와 lambda를 사용해 특정요소를 정렬기준으로 삼을 수 있다.

참고: https://infinitt.tistory.com/122

파이썬 람다식

https://wikidocs.net/64

lamda 매개변수: 표현식
위와 같은 형식으로 작성해 가벼운 함수를 정의,호출할 수 있다.
두 수를 더하는 함수를 정의하고 인자로 10,20 을 준다면

(lambda x,y:x+y)(10,20)
#결과 30

위와 같이 사용된다.