[Python] 프로그래머스 - 정렬 - 가장 큰 수 : Case 비교 예시 설명

목차

가장 큰 수

문제 설명

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

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

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

 

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"
[3, 39, 34, 5, 9, 0]	"95393430"
[30, 39, 34, 5, 9, 3]	"953934330"
[0, 0, 0, 0]	"0"

 

소스코드

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

    return str(int("".join(numbers)))

 

문제 풀이 방식

사실상 가장 앞자리가 큰 애들이 먼저 오면 좋다.

Test Case 1번을 참고하면 쉽게 이해된다.

문제는 앞자리가 같은 경우, 그다음 자리가 문제가 된다.

그래서 다음 2 가지 Case를 생각하면 좋다.

1번 Case - [3, 30, 34, 39]

문자열 Sorting 해보아서 알겠지만, 그냥 sort하면 [39, 34, 30, 3] 순서로 출력된다.

실제로 우리가 원하는 결과는 [39, 34, 3, 30] 이다.

자리수가 같지 않아서 3과 30의 비교가 어렵다.

2번 Case - [9, 93, 95, 90]

일반 sorting : [95, 93, 90, 9]

원하는 값 : [9, 95, 93, 90]

Case 종합

두 Case를 비교해보면 한자리 값이 문제가 된다.

1번 Case에서는 3이 중간에 와줘야하고 2번 Case를 보면 9가 맨 앞으로 와줘야한다.

첫 자리가 같은 경우, 두 번째 자리를 비교해줘야 하는데, 한 자리이므로 값이 없어서 비교가 어렵다.

이 부분을 해결하기 위해 동일한 값으로 채워주면 된다.

9를 99로 바꾸고 3을 33으로 바꾸면 위의 결과와 같은 정렬 방식을 얻을 수 있다.

그래서 정렬의 key 값을 key=lambda x: str(x) * 3 으로 설정한 것이다.

numbers의 원소가 0에서 1,000 이하의 숫자이므로 str(x) * 3 을 해서 "9" -> " 999" 이렇게 만들어 준 후 정렬을 한 것이다. 세자리 수를 맞춰주기 위함이다.