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

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"

풀이

문제의 카테고리가 정렬이므로, 정렬만 사용하여 문제를 해결해봅시다. 먼저, 10보다는 6이 유리한 것에서 힌트를 얻어, 맨 앞 자리 수를 기준으로 정렬해봅시다.

numbers = list(map(str, numbers))
numbers.sort(key=lambda v: v[-1], reverse=True)

테스트 1
입력값 〉    [6, 10, 2]
출력 〉    ['6', '2', '10']

테스트 2
입력값 〉    [3, 30, 34, 5, 9]
출력 〉    ['9', '5', '3', '30', '34']

6210은 완성할 수 있지만, 9534330을 완성하기에는 추가 작업이 필요해보입니다. 3, 30, 34는 모두 앞 자리 수가 같고, 주어진 순서대로 정렬되어 있는 것을 볼 수 있습니다. 문제는 3, 30, 34가 합쳐지는 방식입니다.

3과 30은 330과 같이 합쳐졌을 때 303보다 값이 커집니다. 3으로 시작하는 두 자릿수 중 33보다 작은 수는 3의 뒤에 합쳐지는 것이 좋고, 33보다 큰 수는 앞으로 합쳐져야 합니다. 이를 다시 일반화 하면, 다음과 같이 정렬할 수 있습니다.

max_len = len(max(numbers, key=len))
numbers.sort(
    key=lambda v: (v * max_len)[:max_len],
    reverse=True
)

이렇게 정렬하면 주어진 테스트는 통과할 수 있습니다. 하지만 다음과 같은 경우는 어떨까요?

numbers	return
[53, 535]	"53553"

테스트 3
입력값 〉    [53, 535]
출력 〉    ['53', '535']

이대로 합쳐질 경우, 53535가 되어 가장 큰 수라는 조건을 만족시키지 못합니다. 이유는 위 정렬 방법을 사용하면 53과 535는 같은 수로 취급되고, 입력된 순서를 지키기 때문입니다.

53과 535는 어떤 규칙으로 정렬해야 할까요? 단순히 작은 수를 뒤로 보내면 될까요? 53, 535는 합쳤을 때 53553이 되지만, 35, 353은 35353이 되야 합니다. 1의 자리가 큰 순서대로 정렬하면, 이를 만족할 수 있습니다.

numbers = list(map(str, numbers))
max_len = len(max(numbers, key=len))
numbers.sort(key=lambda v: v[-1], reverse=True)
numbers.sort(
    key=lambda v: (v * max_len)[:max_len],
    reverse=True
)

이렇게 풀면... 테스트 11만 통과하지 못합니다. 원인은... 억울합니다. 이거 입출력 예 추가해야 합니다...

numbers	return
[0, 0, 0]	"0"

any를 사용하면, 배열의 값이 모두 0이면 False, 하나라도 0이 아니면 True를 반환합니다. 다음 코드를 함수 제일 앞에 추가하여 0인 경우를 걸러냅니다.

if not any(numbers):
    return '0'

def solution(numbers):
    if not any(numbers):
        return '0'

    numbers = list(map(str, numbers))
    max_len = len(max(numbers, key=len))
    numbers.sort(key=lambda v: v[-1], reverse=True)
    numbers.sort(
        key=lambda v: (v * max_len)[:max_len],
        reverse=True
    )
    return ''.join(numbers)

numbers = [[6, 10, 2], [3, 30, 34, 5, 9], [53, 535], [35, 353], [0, 0, 0]]
for number in numbers:
    print(solution(number))