[프로그래머스 Lv.2] 가장 큰 수 (Python)

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

프로그래머스

풀이

주어진 숫자들을 가지고 가장 큰 수를 만들면 되는 문제이다. 그렇기에 가장 큰 수를 만들 수 있는 방법을 먼저 고민해야 한다.

쉽게 생각할 수 있듯이 높은 자릿수에 큰 수가 위치하면 된다. 그렇기에 배열 내의 숫자를 가장 높은 자릿수의 내림차순으로 정렬하고, 이를 하나로 합치면 된다.

10, 7, 3이 있는 상황을 예로 들어보자. 그렇다면 높은 자릿수에 가장 큰 수가 위치한 7, 3, 10으로 정렬하고 이를 하나로 합친 7310을 반환하면 된다.

다만, 이 경우에 추가적으로 고려해야 할 사항이 있다. 만약 높은 자릿수에 같은 수들이 위치한다면 어떤 순으로 또다시 정렬을 해야 할까? 3, 30, 34가 배열에 존재하는 경우처럼 말이다. 이들을 사용해서 만들 수 있는 가장 큰 수는 34330이므로 34 -> 3 -> 30 순으로 정렬되도록 해야 함을 알 수 있다. 이렇게 정렬되기 위해서는 처음에 생각했던 것처럼 한 자리를 체크하는 것으로는 불가능하고, cmp_to_key 함수를 사용해서 데이터 두 개를 사용하여 정렬하는 방법이 필요하다.

 

cmp_to_key 함수 내의 결과가 양수면 위치를 바꾸고, 음수면 위치를 바꾸지 않는다. 현재 내림차순으로 구현을 원하기 때문에 반대로 생각하여 함수 내의 결과가 음수면 바꿔지고, 양수면 그대로 둔다고 생각해야 한다.

3, 30의 순으로 정렬되어야 하기에 이 두 수의 순서를 바꾸어 합친 값의 차를 이용하도록 하겠다. x를 3, y를 30이라고 하면 x+y=330이고, y+x는 303이다.

이 둘을 사용하여서 cmp_to_key 내의 값이 양수여야 그대로 유지하기 때문에 더 큰 것에서 작은 것을 빼도록, 즉 (x+y) - (y+x)하면 가장 큰 수가 나올 수 있게 정렬할 수 있다.

from functools import cmp_to_key

def solution(numbers):
    numbers = sorted(list(map(str, numbers)), key=cmp_to_key(lambda x, y: int(x+y)-int(y+x)), reverse=True) # key에서 람다함수의 결과가 0보다 작으면 위치를 바꿈
    answer = "".join(numbers)
    if answer == "0" * len(answer): return "0" # 모든 수가 0으로만 이루어진 배열이 입력될 수 있기 때문
    return answer