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

 

1차 시도 사고 과정 - 틀림

• 가장 최고자리 수를 기준으로 정렬을 하여 모든 것들을 Concat하자
• 가장 최고자리 수를 찾기위해 1보다 작아질 때까지 각 수를 나누고 그것을 딕셔너리에 IDx값과 함께 넣자
• {'Index' : 3, 'top_num' : 9} 이런식으로 넣은 후 key를 최고 자리수로 하여서 정렬시키자

-> [3, 30, 34, 5, 9]일 때의 생각울 못했다! 최고자리가 같은 애들이 여러개일 경우 두번째 자리 기준으로 비교가 다시한번 들어가야 한다는 점을 간과하여 틀렸다

 

2차 시도 사고 과정 - 반은 맞음

• numbers에 들어간 값들을 모두 STring으로 변환시키자
• 모든 원소는 0~1000까지의 수이므로 3자리 수가 대부분이다. 
• 3, 34, 32가 있다면 34, 3, 32 순으로 정렬이 되는 것이 옳다
• 35, 354, 355 가 있다면 355, 354, 35 식으로 정렬되는 것이 옳다
• 아스키 코드에 대한 정렬은 첫자리가 같으면 두번째 자리를 비교하는 형태이다.
• 최고 자리로 올라갈수록 높은 수가 많으면 좋은 식이므로 각 수를 3번 반복한 후에 정렬을 시킨다
• 3번 반복하는 이유는 1000초과한 숫자는 없기 때문에 한자리 수를 기준으로 최대 세번 반복시키면 다 비교 가능하기 때문
• 353535, 354354354, 355355355 -> 앞의 두자리가 같으니 세번째 자리 기준으로 다시 정렬한다. 

-> 하지만 마지막 케이스에서 에러가 생겼다.

 

3차 시도 사고 과정 - 맞음

• 케이스 하나를 빠뜨렸다는 것을 확인했다.
• 모든 요소가 0인 경우 '0000'이 출력될 수 있다
• 따라서 00000...00인경우에는 '0'으로 출력되도록 조건을 추가해주어야 한다

sort 메서드

PYTHON의 Sort메서드를 사용하여 (NlogN)시간에 계산되도록 하였다. 

lambda

lambda를 사용하여서 SORT시에만 세개가 반복된 값을 키로 하여 sort하게 만들었다

 

def solution(numbers):
    answer = ''
    array = list(map(str, numbers))
    array.sort(key = lambda x:x*3, reverse=True)
    for a in array:
        answer += a
    if int(answer) == 0:
        return '0'
    return answer

다른 분들 코드를 보았을 때, 문자들을 합치고 0까지 처리하는 좋은 방법이 있길래 추가 수정한다

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