[Day 3] [코딩테스트 연습] 정렬(Sort) - 가장 큰 수

[코딩테스트 연습] 정렬(Sort) - 가장 큰 수

문제 설명

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

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

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

제한 사항

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

입출력 예

문제 해결 방법

1. 빈 문자열로 수를 초기화 한다.
2. 가장 크게 만들 수 있는 수를 고른다(정렬한다).
3. 그 수를 현재 수에 이어 붙인다.
4. 모든 수를 다 사용 할때 까지 반복한다.

"크게 만드는 수"의 기준

예제 1

3, 32, 33, 34가 주어졌다고 가정해보자.

3 vs 32

332(3을 앞에 32를 뒤에) vs 323(32를 앞에 3을 뒤에) 랑 같은 말이다. 332 가 더 크게 만들 수 있는 숫자이기 때문에 3 을 고른다.

3 vs. 33

위 방법과 같이 333 vs 333 과 같아. 즉, 동일한 우선 순위 이다.

3 vs. 34

334 vs. 343이다. 이 경우 343가 더 크므로 34를 선택한다.

예제 2

34, 342, 343, 344가 주어졌다고 가정해보자.

34 vs. 343

위 경우를 살펴 보자. 34343(34 왼쪽, 343 오른쪽) vs. 34334(343 왼쪽, 34 오른쪽) 이 때는 34343이 더 크므로 34를 골라야한다.

정리

즉, 정렬을 할 때 이러한 기준으로 비교를 해서 정렬을 해야한다.

34 vs 343

34의 경우, 수를 가장 크게 만드는 것을 우선으로 정렬이 되었있다고 가정하면, 34보다 뒤에 올 수있는것은 커 봐야 34를 넘지 못한다. 그걸을 쭉 이어 붙히면 3434343434...이런 반복이 된다.

343의 경우 이것을 쭉 이어 붙히면 343343343343이런꼴이 된다. 문제의 제안 조건이 1000이하 이기 때문에 길어 봐야 4글자이다. 4글자를 끈어서 비교하면된다.

코드 구현

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers = list(sorted(numbers, key=lambda x: (x*4)[:4], reverse=True ))
    return str(int("".join(numbers)))