프로그래머스 Lv.2: 가장 큰 수 - Python 풀이

문제 설명

프로그래머스

0 또는 양의 정수들이 배열로 주어졌을 때, 주어진 정수들을 이어붙여 만들 수 있는 가장 큰 수를 반환해야 한다. 주어진 조건은 아래와 같다.

• 입력값 numbers의 길이는 1 이상 100,000 이하
• numbers의 원소는 0 이상 1,000 이하
• 정답이 너무 클 수 있으니 문자열로 바꿔서 반환

예) 입력: [6, 10, 2] / 반환: "6210"

6, 10, 2를 이어붙여 만들 수 있는 수는 6102, 6210, 1062, 1026, 2106, 2610 이 있고, 이 중 가장 큰 수는 6210이다.

풀이 과정

일단 생각나는 접근법은 맨 앞자리 수가 가장 큰 수가 들어가면 되겠다. 위의 예시에서 보면 6, 10, 2 중 가장 큰 수는 10임에도 불구하고 10이 맨 앞에 놓이면 1이 맨 앞자리 수가 되기 때문에 이어붙인 전체 값은 작아진다.

1. 숫자 배열을 문자열 배열로 변환하여 자릿수에 관계없이 큰 숫자가 앞에 오면 앞에 정렬되도록 한다.
2. 추가적으로 "30"과 "3"과 같은 경우를 대비하기 위해, sort의 key를 x*3으로 두어 각 숫자를 3번 반복한 값을 기준으로 내림차순 정렬한다. ("30"보다 "3"을 앞에 두는 것이 더 큰 수를 만들기 때문이다.) -> 문자열을 인위적으로 확장해서 자리수 차이를 보완하는 것!

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

numbers의 원소는 최대 1000이기 때문에 각 숫자를 3번씩 반복해서 비교하면 자릿수의 영향을 제거할 수 있다.
예: "3" → "333", "30" → "303030" => "3"이 "30"보다 더 앞에 올 수 있게 된다.

만약 *2였으면? "2"랑 "220"이 있었을 때 "22", "220220" 이렇게 돼서 "220"이 더 앞으로 가게 된다.
*3이면? "222", "220220220" 이라서 "2"가 "220"보다 더 앞으로 가게 된다.
*4였다면? "2222", "220220220220"으로 "2"가 "220"보다 더 앞으로 가게 된다.
즉, 최소 3번만 반복해 주면 된다.