[Python] 가장 큰 수

1. 문제

 

 

 

2. 풀이 과정

개인적으로 테스트 케이스들을 생각해보는 게 알고리즘을 떠올리기가 좋았다.

 

[CASE1]

두 수 비교부터 생각해보면, [35, 3443]이 있다고 가정하자.

참고로, 숫자와 달리 문자열은 아스키코드에 따라 인덱스 0번째부터 비교해간다. 오름차순으로 정렬하면 [3443, 35]가 되며 큰 수부터 나열하면 정답인 "353443"을 반환한다.

 

[CASE2]

그러면 [34, 3421]인 경우를 생각해보자. 이미 정렬된 상태로 정답인 "343421"과 다른 "342134"를 반환한다. 여기 문제는 34의 자릿수가 적어서 발생한다. 문자열 정렬과 위 문제는 이 부분에서 차이가 난다.

 

결론

CASE1)처럼 자릿수가 끝나기 전에 그 자릿수까지의 숫자가 달라서 정렬이 되면 상관없지만, 그 자릿수까지 같으면 없는 자릿수는 패턴으로 비교해야 한다. [3434, 3421]을 비교해야 된다는 것이다.

해당 자릿수까지 같은 수가 있을 때 그 뒷자리까지 비교되므로, 같은 수인 지점까지 뒤에 복사해서 붙여주는 것이다. 즉,  34 + 3421이 클지 3421 + 34가 클지 비교하는 것과 같다.

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers = sorted(numbers, key = lambda x:(x*4)[:4], reverse = True)
        
    answer = ''.join(numbers)
        
    #"0000" => 숫자로는 "0"
    if answer[0] == "0":
        answer = "0"
    
    return answer