[정렬] 프로그래머스 Lv2. 가장 큰 수 - Python

🗂️ 문제

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

 

💡 접근법

주어진 숫자 리스트를 이어붙여 만들 수 있는 모든 경우의 수를 탐색하면 시간 초과가 발생한다.
따라서 문자열 정렬을 활용해 가장 큰 수를 만들어야 한다.

 

문자열 정렬의 특성
- 문자열 정렬은 숫자의 크기나 자릿수와 상관없이 문자 순서대로 사전식 정렬된다.
- 문자열의 길이가 다를 때, 더 짧은 문자열은 사전식 정렬에서 먼저 온다. 
   ex) "1"과 "10"을 비교하면, "1"이 "10"의 부분 문자열이므로 "1"이 "10"보다 앞에 정렬된다.

 

올바른 정렬을 수행하기 위해 자릿수를 맞춰서 비교해야 한다.

• 문자열 정렬은 사전식 정렬로 수행되므로, 이는 [1, 10] 경우와 같이 원하는 정렬을 수행할 수 없다.
  [1, 10]을 내림차순 정렬하면 [10, 1]이 되며, 이를 이어붙이면 101이 되므로 가장 큰 수를 만들 수 없다.
• 문제에서 숫자의 최대값이 1000이므로, 최소 3자리 이상으로 맞춰야 하며, 이를 위해 각 숫자를 3번 반복하여 비교한다.
• 한 자리의 자릿수를 가지는 원소 “3”이 있을 때, 이는 3번 이어붙이면 “333”이 된다. 만약 4번 이어붙이게 될 경우 “3333”이 되며, 이는 최댓값을 넘어간다.

 

정렬 과정 예시

1. [303, 30, 3]의 각 원소를 3번 반복하여 변환:
   • 303 → "303303303"
   • 30 → "303030"
   • 3 → "333"
2. 이를 기준으로 내림차순 정렬:
   → 정렬 결과: ['333', '303303303', '303030']
3. 원본 값 복구 후 이어붙이면 330330이 되어 가장 큰 수가 완성된다.

 

😎 내 코드

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(reverse=True, key=lambda x: x*3)
    return str(int("".join(numbers)))

마지막에 이어붙인 문자열을 str(int())하는 이유는 [0, 0]의 경우를 처리하기 위해서다. (“00” → “0”으로)