프로그래머스 Lv.2 | Python | 가장 큰 수

1. 문제 정보

프로그래머스

• 난이도: Lv.2

---

2. 문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

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

제한 조건

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

---

3. 접근 기준

이 문제는 단순 내림차순 정렬로 해결되지 않는다.

예를 들어:

[3, 30]

 

숫자 크기만 보면 30이 더 크지만,

330
303

 

실제로는 3이 앞에 와야 더 큰 수가 된다.

즉, 이 문제는 숫자 자체 비교가 아니라:

a+b 와 b+a 비교

 

를 기준으로 정렬해야 한다.

---

4. 사용한 패턴 / 알고리즘

커스텀 정렬 (Custom Sort)

• 두 문자열을 이어붙여 비교
• 더 큰 조합이 앞에 오도록 정렬

cmp_to_key

• 비교 함수를 sort에서 사용할 수 있게 변환

---

5. 핵심 아이디어

핵심은 두 숫자의 순서를 직접 비교하는 것이다.

예:

3 + 30 = 330
30 + 3 = 303

 

330 > 303 이므로:

3이 앞

 

• a+b > b+a → a가 앞
• a+b < b+a → b가 앞

이 기준으로 전체를 정렬하면 된다.

---

6. 풀이 코드

from functools import cmp_to_key

# cmp_to_key에 전달할 비교 함수
# a, b 두 값을 비교해서 어떤 값이 앞에 와야 하는지 결정한다.
def compare(a, b):

    # a + b가 b + a보다 크면
    # a를 앞에 두는 것이 더 큰 수를 만들 수 있다.
    if a + b > b + a:
        return -1  # a가 b보다 앞에 와야 함

    # a + b가 b + a보다 작으면
    # b를 앞에 두는 것이 더 큰 수를 만들 수 있다.
    elif a + b < b + a:
        return 1   # b가 a보다 앞에 와야 함

    # 두 경우가 같으면 순서를 바꾸지 않아도 된다.
    else:
        return 0

def solution(numbers):

    # 숫자를 문자열로 변환한다.
    # 이어붙인 결과를 비교해야 하므로 문자열 비교가 필요하다.
    numbers = list(map(str, numbers))

    # 파이썬의 sort는 기본적으로 key 함수만 받는다. 그런데 이 문제는 각 원소 하나의 기준값이 아니라,
    # 두 원소 a, b를 직접 비교해야 한다.
    
    # cmp_to_key(compare)는 compare 함수를 sort에서 사용할 수 있는 key 형태로 바꿔주는 역할을 한다.
    
    # compare(a, b)의 반환값 의미:
    # -1 → a가 b보다 앞
    #  1 → b가 a보다 앞
    #  0 → 순서 유지
    
    numbers.sort(key=cmp_to_key(compare))

    # 정렬된 문자열을 하나로 이어붙인다.
    answer = ''.join(numbers)

    # [0, 0, 0]인 경우 answer는 "000"이 된다.
    # 그대로 반환하면 "000"이므로 int로 바꿨다가 다시 str로 변환한다.
    return str(int(answer))

cmp_to_key는 두 값을 직접 비교하는 함수를 정렬 기준으로 사용할 수 있게 바꿔주는 함수다. 일반적인 sort(key=...)는 원소 하나를 받아 정렬 기준값을 만든다. 하지만 이 문제는 3과 30처럼 두 값을 직접 붙여보고 330이 큰지 303이 큰지 비교해야 한다. 그래서 compare(a, b)처럼 두 값을 비교하는 함수를 만들고, 이를 cmp_to_key(compare)로 감싸서 정렬에 사용한다.

---

7. 핵심 로직 요약

이 문제의 핵심은 숫자 크기가 아니라 이어붙인 결과를 기준으로 정렬하는 것이다.

• 숫자를 문자열로 변환한다.
• a+b 와 b+a를 비교한다.
• 더 큰 조합이 앞에 오도록 정렬한다.
• 정렬된 문자열을 이어붙인다.
• "000" 같은 경우를 처리하기 위해 int() 후 다시 문자열 변환한다.

결국, “이어붙인 결과 비교 + 커스텀 정렬” 이 구조가 핵심이다.

---

8. 정리

처음 보면 그냥 내림차순 정렬 문제처럼 보인다. 근데 실제로는 숫자 크기 자체가 의미가 없어서 바로 막힌다.

특히 이 부분이 핵심이었다.

3 과 30 중 뭐가 앞인가?

 

이걸 숫자 비교로 접근하면 계속 틀리고, 문자열을 이어붙여 비교해야 한다는 걸 떠올려야 풀린다.

또 처음엔 cmp_to_key가 낯설어서 어렵게 느껴질 수 있는데,
실제로는:

• “두 값을 직접 비교해서 정렬 기준을 만든다”

이 역할만 이해하면 된다.

결국 이 문제는 정렬 자체보다도, “무엇을 기준으로 비교해야 하는가”를 찾는 문제라는 느낌이 강했다.