[정렬] 가장 큰 수 (프로그래머스, Level2)

문제

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

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

• 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

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

입력 예시 및 제한사항

풀이

💡 아이디어

• numbers 배열 각 숫자의 최대 자리수 : 3자리 (1000만 4자리 숫자이므로 이를 제외하고 최대 자리수는 3자리이다)
• numbers 배열의 각 요소를 3자리로 맞춰준다. (각 요소를 반복하면서)
  : 3자리씩 맞춰준 숫자를 리스트에 저장할 필요는 없고, 증가시킨 값을 기준으로 정렬만 시키면 된다.
• ex) 3 : 333, 31 : 313..., 310 : 310...
• 바꿔준 숫자를 비교하면서 큰 값을 앞으로 두고 숫자를 조합한다.

✏️ 아이디어 참고

문제 풀이 아이디어를 잘 작성해놓은 아래 블로그들을 참고하면 더욱 효과적으로 이해할 수 있을 것이다.

문제 풀이 아이디어(1)
➡️ 위 게시글에 원리가 아주 잘 정리되어있다.

문제 풀이 아이디어(2)

코드

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))       # numbers 배열의 요소들을 str형태로 변환한다.
    numbers.sort(key = lambda x : x*3, reverse=True)      # x값(숫자)를 세 번 곱해서 문자열 길이를 3배로 늘린 값을 기준으로 정렬한다. 이때 비교가 값의 크기로 비교되는 것이 아니라, 앞에서 세 자리까지의 문자의 크기에 따라 정렬된다.
    # ex) 3 => 333과 31 => 313131 이 있으면, 33과 31까지 중에서 3>1인 경우가 발생하므로, 3이 31보다 앞에 정렬된다.
    answer = str(int("".join(numbers)))     # 정답을 문자열로 리턴하라고 한다.
    
    # answer은 다음과 같이도 표현 가능하다.
    # answer = str(int(answer.join(numbers)))   # int()형으로 변환하지 않으면 오류가 발생한다.
    return answer