문제 28 - 가장 큰 수 (Python)

프로그래머스

주어진 정수들을 이어 붙였을 때 만들 수 있는 가장 큰 수를 문자열로 반환하는 문제입니다.
핵심은 숫자 자체의 크기가 아니라, 두 숫자를 어떤 순서로 붙였을 때 더 큰 문자열이 되는지를 기준으로 정렬하는 것입니다.

---

1. 나의 풀이

from functools import cmp_to_key


def compare(a, b):
    if a + b > b + a:
        return -1
    elif a + b < b + a:
        return 1
    else:
        return 0


def solution(numbers):
    str_nums = list(map(str, numbers))

    answer = ''.join(sorted(str_nums, key=cmp_to_key(compare)))

    if answer[0] == '0':
        return '0'

    return answer

이 풀이에서는 먼저 숫자를 문자열로 변환했습니다.
숫자를 이어 붙여 비교해야 하므로, 정수 덧셈이 아니라 문자열 결합이 필요하기 때문입니다.

정렬 기준은 compare 함수에 따로 분리했습니다.

a + b > b + a

예를 들어 "3"과 "30"을 비교하면 다음과 같습니다.

"3" + "30"  # "330"
"30" + "3"  # "303"

"330"이 더 크므로 "3"이 "30"보다 앞에 와야 합니다.

cmp_to_key(compare)는 이렇게 두 값을 직접 비교하는 함수를 sorted()의 key 인자로 사용할 수 있게 바꿔주는 역할을 합니다.

---

2. 오늘 배운 점 및 복기 노트

숫자 크기 기준 정렬로는 풀 수 없습니다

이 문제는 단순히 큰 숫자를 앞에 두는 문제가 아닙니다.
예를 들어 [6, 10, 2]를 숫자 기준으로 내림차순 정렬하면 [10, 6, 2]가 되지만, 이어 붙이면 "1062"가 됩니다.

정답은 "6210"입니다.
따라서 숫자 자체가 아니라 이어 붙인 결과를 기준으로 비교해야 합니다.

 

두 숫자의 순서는 직접 붙여 보면 됩니다

a와 b 중 어떤 값이 앞에 와야 하는지는 다음 비교로 판단할 수 있습니다.

a + b > b + a

a + b가 더 크면 a가 앞에 와야 합니다.
b + a가 더 크면 b가 앞에 와야 합니다.

이 기준이 문제의 핵심입니다.

 

compare 함수의 반환값 방향을 주의해야 합니다

cmp_to_key에서 비교 함수는 반환값으로 순서를 결정합니다.

return -1

a가 b보다 앞에 와야 한다는 뜻입니다.

return 1

b가 a보다 앞에 와야 한다는 뜻입니다.

 

그래서 이 문제에서는 a + b가 더 클 때 -1을 반환했습니다.
가장 큰 문자열을 만들기 위해 더 앞에 두어야 하기 때문입니다.

---

모든 값이 0인 경우를 처리해야 합니다

입력이 [0, 0, 0]이면 정렬 후 결과는 "000"이 될 수 있습니다. 하지만 문제에서 원하는 정답은 "0"입니다.

정렬 결과의 첫 글자가 "0"이라면 모든 값이 0이라는 뜻입니다.

if answer[0] == '0':
    return '0'

내림차순 정렬 기준에서 가장 앞의 값이 0이면, 뒤의 값들도 모두 0입니다.

---

3. 프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

순열로 모든 경우를 만들면 시간 초과가 발생합니다

처음에는 모든 숫자의 순서를 만들어 가장 큰 값을 찾는 방식을 생각할 수 있습니다.
하지만 numbers의 길이는 최대 100,000입니다.

순열은 경우의 수가 급격히 증가하므로 이 문제에서는 사용할 수 없습니다.
이 문제는 모든 배치를 만들어 보는 문제가 아니라, 올바른 정렬 기준을 찾아야 하는 문제입니다.

 

cmp_to_key는 정렬 기준을 직접 표현할 수 있습니다

일반적인 key 정렬은 원소 하나를 기준값으로 바꿔 정렬합니다.
하지만 이 문제는 원소 하나만 봐서는 순서를 판단하기 어렵습니다.

예를 들어 "3"과 "30"은 각각 따로 보면 어느 쪽이 앞에 와야 하는지 애매합니다.
하지만 두 값을 붙여 보면 판단할 수 있습니다.

"330" > "303"

이처럼 두 원소를 직접 비교해야 하는 문제에서는 cmp_to_key가 유용합니다.

 

비교 함수 방식은 명확하지만 비용이 있습니다

cmp_to_key를 사용하면 문제의 핵심 기준을 코드로 명확하게 드러낼 수 있습니다.

if a + b > b + a:
    return -1

다만 정렬 과정에서 비교 함수가 여러 번 호출되므로, 단순한 key 정렬보다 실행 시간이 느릴 수 있습니다.

문제를 이해하고 기준을 정확히 세우는 데에는 좋은 풀이지만, 성능 최적화가 필요하다면 문자열 반복을 이용한 key 정렬도 고려할 수 있습니다.

 

문자열 반복 key 방식의 아이디어

숫자의 범위가 0 이상 1000 이하이므로 문자열을 반복해서 비교 기준을 만들 수도 있습니다.

def solution(numbers):
    numbers = list(map(str, numbers))

    numbers.sort(key=lambda x: x * 4, reverse=True)

    result = ''.join(numbers)

    if result[0] == '0':
        return '0'

    return result

이 방식은 직접 비교 함수를 호출하지 않고, 파이썬의 문자열 정렬 기준을 활용합니다.
따라서 일반적으로 cmp_to_key 방식보다 더 빠를 수 있습니다.

다만 이 풀이는 문제의 제한 조건을 활용한 방식입니다.
숫자의 최대 자릿수가 달라지면 반복 횟수도 함께 다시 생각해야 합니다.

 

int() 변환보다 첫 글자 확인이 가볍습니다

모든 값이 0인 경우를 처리할 때 다음처럼 작성할 수도 있습니다.

return str(int(''.join(numbers)))

하지만 정답 문자열이 매우 길 수 있으므로, 큰 문자열을 정수로 변환하는 과정은 부담이 될 수 있습니다.

이 문제에서는 정렬 결과의 첫 글자만 확인해도 충분합니다.

if answer[0] == '0':
    return '0'

불필요한 형 변환을 줄이면 더 가볍게 예외 처리를 할 수 있습니다.

 

정렬 문제는 기준을 세우는 것이 핵심입니다

이 문제에서 중요한 것은 정렬 함수를 사용하는 것 자체가 아닙니다.
어떤 값이 앞에 와야 최종 문자열이 커지는지 기준을 세우는 것이 핵심입니다.

복기할 때는 다음 기준만 기억하면 됩니다.

a + b > b + a

두 문자열을 직접 붙여 보고 더 큰 쪽이 되는 순서로 정렬하면 됩니다.