[programmers/python] 정수를 이어 만들 수 있는 가장 큰 수 - 문자열 정렬

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

"가장 큰 수 만들기" 문제는 자주 등장하는 정렬 응용 문제이며, 문제의 겉모습은 간단하지만 내부에 숨겨진 비교 로직을 정확히 이해하는 것이 핵심이다.

---

문제 정의

0 또는 양의 정수가 담긴 배열 numbers가 주어졌을 때, 해당 수들을 조합하여 만들 수 있는 가장 큰 수를 문자열 형태로 반환하라.

예시:

numbers = [6, 10, 2]
# 만들 수 있는 조합 중 가장 큰 수: 6210

 

 

해결 아이디어

일반적인 정렬로는 해결할 수 없다. 왜냐하면, 단순히 수의 크기만 비교할 경우 [30, 3]과 같은 경우 30 > 3이므로 303이 만들어지지만, 실제로는 330이 더 크기 때문이다.

따라서 두 수 a, b를 비교할 때는 문자열로 바꾼 후 a+b와 b+a 중 어떤 조합이 더 큰지를 기준으로 정렬해야 한다.

핵심 구현

Python의 문자열 비교 특성을 활용하여 정렬 기준을 정의할 수 있다.
또한, 문제에서 주어진 수는 최대 1,000이므로 문자열을 3번 반복한 값을 기준으로 정렬해도 정렬 순서에 문제가 없다.

def solution(numbers):
    numbers = list(map(str, numbers))  # 숫자를 문자열로 변환
    numbers.sort(key=lambda x: x * 3, reverse=True)  # 정렬 기준 정의
    return str(int(''.join(numbers)))  # '0000' 방지를 위해 int → str 재변환

 

 

테스트 예시

print(solution([6, 10, 2]))            # "6210"
print(solution([3, 30, 34, 5, 9]))     # "9534330"
print(solution([0, 0, 0]))             # "0"

 

 

정리

• 두 숫자 a, b를 붙였을 때 ab와 ba 중 어떤 것이 더 큰지를 비교 기준으로 삼는다.
• Python의 sort 함수는 문자열 비교를 기반으로 정렬하므로, 문자열 반복으로 길이를 맞춰주면 비교가 가능하다.
• 최종 결과가 "000"처럼 될 수 있으므로, int()로 변환 후 str()로 다시 변환하면 "0"으로 정상화된다.