문제 설명
•
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내는 문제
예제 입력/출력
numbers | return |
[6, 10, 2] | "6210" |
[3, 30, 34, 5, 9] | "9534330" |
[0,0,0]
히든 케이스 | “0” |
제약 조건
•
◦
원소
•
문자열로 바꾸어 return
문제 풀이
접근1 브루트 포스 (완전 탐색) -
•
접근2 정렬 -
◦
숫자를 문자열로 변환해준 다음 문자열 길이를 3배로 늘린 후에 내림차순 정렬을 진행한다.
▪
왜 숫자를 문자열로 변환해주는가?
•
숫자 크기로 정렬하면 원하는 순서를 만들 수 없음
◦
예: [3, 30, 34]을 숫자로 정렬하면 [3, 30, 34]이지만, 우리가 원하는 정렬은 [34, 3, 30]
•
따라서, 문자열로 변환 후 직접 비교하여 정렬하는 방법이 필요함
▪
왜 문자열을 3배로 늘려야 할까?
•
일반적으로 문자열 비교 (”3” > “30”)를 이용해서 정렬하면, 앞자리부터 차례대로 비교한다.
•
하지만 숫자를 단순히 문자열로 변환해서 비교하면 이 문제에서 원하는 대로 정렬되지 않는 경우가 발생한다.
◦
예: [”3”, “30”]
▪
단순 문자열 비교 시 → 30 > 3
•
짧은 문자열이 긴 문자열의 접두사(prefix)일 경우, 짧은 문자열이 더 작다고 판단됨.
▪
문자열을 3배 확장 후 비교 시 → 3 > 30
•
문자열 333과 문자열 303030을 비교하면 333이 더 크다고 판단
•
우리가 원하는 이상적인 정렬!
풀이 코드
def solution(numbers):
numbers = list(map(str, numbers)) # 숫자를 문자열로 변환
numbers.sort(key=lambda x: x * 3, reverse=True) # 숫자를 3자리 이상으로 반복 확장 후 정렬
return str(int("".join(numbers))) # "0000" 같은 경우 "0" 처리
Python
복사