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

🔗 문제 링크

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

📰 문제 요약

문제 설명, 입력, 출력, 조건 등 간략하게 정리

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내기

입력

정수가 담긴 배열 numbers

출력

정답이 너무 클 수 있으니 문자열로 바꾸어 return

🔓 문제 접근 방식

기본 아이디어

• 정렬인데,,, 정렬아닌,,, 첫 자리가 큰 숫자부터 봐야할 것 같다!

사용 알고리즘

• 정렬 알고리즘

💻 구현 방법

1. 기본 아이디어

정수를 조합하여 가장 큰 수를 만들기 위해서는 숫자의 순서를 적절히 배치하는 것이 중요

숫자를 이어 붙일 때 큰 값이 나오도록 정렬해야하기 때문에 두 숫자를 이어 붙였을 때 더 큰 수가 만들어지는 순서대로 정렬

---

2. 정렬 기준 정의

기본적인 숫자 크기 비교가 아니라, 두 숫자를 이어 붙였을 때 더 큰 값이 되도록 비교해야 하기 때문에 커스텀 비교 함수를 정의

두 숫자 x, y를 비교하는 방법:

1. x + y와 y + x를 비교
   • 예를 들어 x = "3", y = "30"이면:
     • "330" (x가 앞) vs "303" (y가 앞)
   • "330"이 더 크므로 x가 앞에 와야 함.
2. 정렬할 때 x + y > y + x이면 x가 앞,x + y < y + x이면 y가 앞에 오도록 설정.

👍🏻 최종 제출 코드

from functools import cmp_to_key

def compare(x, y):
    if x + y > y + x:  # x를 앞에 두는 경우가 더 큰 수가 되는 경우
        return -1
    elif x + y < y + x:  # y를 앞에 두는 경우가 더 큰 수가 되는 경우
        return 1
    else:
        return 0

def solution(numbers):
    numbers = list(map(str, numbers)) # 숫자를 문자열로 변환    
    numbers.sort(key=cmp_to_key(compare)) # 정렬 (커스텀 비교 함수 사용)
    result = ''.join(numbers) # 정렬된 리스트를 합쳐서 결과 반환
    return '0' if result[0] == '0'else result # "0000" 같은 경우를 방지

📝 새로 학습한 내용

이런 유형이 처음 나와서 굉장히 막막했는데, 굉장히 고전적인 풀이가 있었다!

구현 방식을 간단하게 정리하면,

✅ 숫자를 문자열로 변환한 후, 이어 붙였을 때 더 큰 값을 기준으로 정렬한다.

✅ 정렬 기준: (x+y) > (y+x)를 비교하여 내림차순 정렬을 수행한다.

✅ 모든 숫자가 0일 경우 "0"을 반환하는 예외 처리가 필요하다.

def compare(x, y):
    if x + y > y + x:  # x를 앞에 두는 경우가 더 큰 수가 되는 경우
        return -1
    elif x + y < y + x:  # y를 앞에 두는 경우가 더 큰 수가 되는 경우
        return 1
    else:
        return 0

해당 방식을 통해, 숫자를 문자로 변환한 것을 비교하는 방식으로 구현할 수 있었다.

cmp_to_keys

• cmp_to_key는 사용자 정의 비교 함수를 sort()에서 사용할 수 있도록 변환해준다.
• sort()는 기본적으로 비교 연산자 <만 지원하는데, <, >를 다루기 때문에 중요하다.

📚 참고 자료

https://velog.io/@heyday_7/python-조건-정렬-하기-cmptokey