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

 

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

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

아이디어

• 문자열 A+B, 로 만든 숫자와 B+A로 만든 숫자를 비교하여 어느게 더 큰수인지 확인하고 정렬한다
• 파이썬 문자열 비교를 이용하면 사전순으로 정렬해주는데 이걸 수 비교수단으로 이용할 수 있다
• 답이 0일 경우에는 0만 리턴해준다.(마지막 테스트 케이스)

 

from functools import cmp_to_key

def mycmp(A, B):
    sA = str(A)
    sB = str(B)
    if sA + sB < sB + sA:
        return 1
    else:
        return -1

def solution(numbers):
    numbers.sort(key = cmp_to_key(mycmp))
    numbers = list(map(str,numbers))
    answer = ''.join(numbers)
    if answer[0] == '0':
        return "0"
    return answer

 

 

 

 

다른사람 풀이를 보니 개쩌는 풀이를 발견했다.

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

 

이해하는데 한참 걸렸다.

 

위 코드 내용을 예제 기반으로 설명하자

 

예제에서 정렬하기가 어려운 케이스가 3, 30, 34 를 어떤식으로 정렬하나 이다.

 

결론을 말하면

 

간단히 생각하면, 작은숫자를 가진 숫자는 무조건 뒤로 보내는게 유리하다.

 

34는 4를 가지고 있으므로 가장 앞으로 보내는게 좋고 30은 0을 가지고 있으므로 뒤로 보내는게 좋다.

 

3, 30, 34 의 경우 앞자리가 3이 같고 뒤에는 30은 뒤에 0, 34는 뒤에 4가 있다.

 

그래서 정렬순은 4가 3보다 크고 0이 3보다 작으므로

 

34, 3, 30 이 되어야한다.

 

 

 

 

 

숫자 A, B가 있다 하자.

 

주어진 행렬이 [ A, A, A, A, A, B, B, B, B, B ] 이렇게 있다 하자.

 

그럼 답은 AAAAABBBBB 혹은 BBBBBAAAAAA 일 것이다.

 

그럼 AAAAA, BBBBB 부분만 비교해봐도 거진 답은 결판난다.

 

 

 

 

 

 

그럼 저 3이라는 숫자는 어떻게 잡을까?

 

문자열을 반복 할 때 달라지는 시점까지 나오는 숫자를 잡으면 된다

 

허나 그건 문자열이 어떻게 주어지냐에 따라 다르다

 

가령

 

3, 30 의 케이스의 경우에는 곱하기 2만 해줘도 문자열이 비교가 된다.

 

33

30

 

1, 112 의 경우에는 곱하기 3을 해줘야 한다.

 

111

112

 

 

즉 최악의 케이스, 가장 큰 수를 잡아주면 된다.

 

 

 

문제에서는 1000 이하의 자연수라고 했다.

 

가장 최악의 케이스는 3이 될 것이다.

 

ex)

1 <-> 112

9 <-> 998

 

 

 

어 근데 1000은 4자리 숫자인데 곱하기 4 해줘야 되는거 아니야? 라고 하겠지만

 

1000은 4자리숫자중 가장 작은 숫자이기에 3만 해줘도 되는것으로 보인다.

 

 

가령 범위가 9999 이하의 숫자였다면 곱하기 4를 해줘야 하는게 맞다.

 

ex) 9 <-> 9998