[프로그래머스] 가장 큰 수 (정렬 Lv.2) - Python

문제

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

프로그래머스

문제설명

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

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

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

 

제한사항

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

 

입출력 예

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

풀이

접근

처음엔 그냥 정렬하면 되겠지, 생각했다.

리스트들을 돌면서 가장 큰 수를 만들면 되는 거 아닌가? 했는데

생각해보니 이건 자릿수에 함정이 있었다.

이어붙인다고 생각하면, 당장 numbers 리스트에 들어있는 수가 큰 것이 중요한 게 아니다.

이어 붙이면 어차피 자릿수는 같으니 결국 앞자리에 오는 숫자 하나하나가 커야 한다.

numbers = [3, 30, 34, 5, 9] 의 예시에서,
30과 9를 비교하면 이어 붙일 땐 9를 앞에 붙여야 한다.

그러므로 sorted 를 사용해 문자열로 변환해 비교한다.

문자열로 비교하면 맨 앞자리부터 비교하므로, sorted(['30','9'],reverse=True) 를 하면 ['9','30'] 이 되기 때문이다.

그런데 30과 3처럼 앞자리가 같은 애들은 30이 먼저 정렬되게 된다.

하지만 이어 붙인다고 생각하면 330 > 303 이기 때문에 3이 앞에 와야 하는데,

그러려면 이 숫자들이 높은 자릿수에 있을 때를 가정해서 비교해야 한다는 거다. (3이 더 높은 자릿수일 때 > 30이 더 높은 자릿수일때 )

따라서 문자열을 세번 반복해 이어붙이면 뒷자리는 상관없이 높은자리로 가정해서 비교할 수 있다.

sorted(['30','3'])는 ['30','3']이 되지만, sorted(['303030','333'])은 ['333', '303030'] 이기 때문

def solution(numbers):
	# 3번씩 이어 붙인 문자열들을 내림차순으로 정렬
    numbers = sorted(numbers, key=lambda x: str(x)*3, reverse=True)
    
    #문자열들을 전부 이어 붙인다.
    answer = ''.join(map(str, numbers))

이렇게 완성했는데,

실패한 테스트 케이스가 있었다.

도저히 어디서 문제가 생긴 건지 모르겠어서 질문하기에 들어가봤는데,

['0', '0',  '0',  '0'] 처럼 모든 원소가 0인 반례가 있다는 것...

나는 아직 멀었다...

아무튼 그래서 해당 조건을 추가해주고 다시 완성했다.

풀이 코드

def solution(numbers):
	# 3번씩 이어 붙인 문자열들을 내림차순으로 정렬
    numbers = sorted(numbers, key=lambda x: str(x)*3, reverse=True)
    
    #문자열들을 전부 이어 붙인다.
    answer = ''.join(map(str, numbers))
    
    # numbers의 원소가 모두 0일 때
    return answer if int(answer) != 0 else '0'