42746. 가장 큰 수 / python / 커뮤러닝 5기 코딩테스트 실력 UP 패키지 : 문제 풀이 꿀팁과 실전 모의고사

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

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예numbersreturn

[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

---

※ 공지 - 2021년 10월 20일 테스트 케이스가 추가되었습니다.

 

풀이 1 - 실패 

from collections import defaultdict

def solution(numbers):
    answer = ''
    numbers_dic=defaultdict(list)

    #맨 앞자리 수를 키로 갖는 딕셔너리
    for n in numbers:
        i=n
        while i>=10:
            i=i//10 
        numbers_dic[i].append(n)

    keys=sorted(numbers_dic.keys(),reverse=True)

    for k in keys:
        nums=[]
        for n in numbers_dic[k]:
            last_num=str(n%10)
            n_copy=str(n)
            while len(n_copy)<5:
                n_copy+=last_num
            nums.append((n,int(n_copy)))
        nums=sorted(nums,key=lambda x : x[1], reverse=True)
        for n in nums:
            answer+=str(n[0])
        
    return answer

n이 1000이하의 수 이므로 이를 푼다. 

실패한 이유 : 만약 [1,10,100,1000]의 경우 모두 마지막 숫자를 확장했을 때 1000으로 같다. 그러므로 sort 할 때 틀린다.

테스트 1,2,3,4,5,6,11 에서 오류가 났다. 

그러므로 nums를 정렬할 때 확장한 수의 결과가 같다면 제일 짧은 수를 먼저 정렬하는 방법을 추가해야 한다.

내가 생각했던 테스트 케이스를 통과했지만 위와 같은 테케는 통과하지 못했다. 

 

테스트 케이스 11번 [0,0,0,0] --> "0" 

:return 문을 수정해서 해결하였다. / 위의 코드를 좀 더 깔끔하게 작성하였다. 

from collections import defaultdict

def expand_num(n):
    n=int(str(n)+str((n%10))*(4-len(str(n))))
    return n

def solution(numbers):
    answer=''
    number_dic=defaultdict(list)

    for n in numbers:
        number_dic[str(n)[0]].append(n)
    for s in number_dic:
        number_dic[s]=sorted(number_dic[s],key=lambda x : (expand_num(x),-len(str(x))),reverse=True)

    for s in sorted(number_dic,reverse=True):
        answer+=''.join(map(str,number_dic[s]))

    return str(int(answer))

테스트 케이스 1~6 번 

[233,23] -> "23323"

끝 수를 늘릴 경우 둘다 2333,2333 이 되고 길이를 비교할 경우 더 짧은 23이 앞에 오게 되어 23233이 된다. 그러나 23323이 더 큰 수이다. 길이를 비교해 짧은 코드를 앞에 정렬하는 코드는 [1,10,100,1000]의 경우를 위해 추가된 코드이므로 두 케이스가 상반된다. 

 

차라리 처음부터 다시 생각해 보자면 

10,100 의 경우 앞 자릿수가 더 크기 때문에 길이가 짧은 수가 먼저 와야 맞고 

23,233의 경우 뒷자리가 더 크기 때문에 길이가 긴 수가 먼저 와야 맞다  

위의 것을 판별하는 함수를 따로 짜서 차라리 람다식의 두 번째 비교 인자로 줄까 했는데 한 자릿수의 숫자의 경우 애매했다 

 

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

위의 식은 다른분의 식을 참고한 식이다. 이런 식으로 str의 특성을 이용해서 풀이하면 간단하게 풀 수 있다.