출처: https://programmers.co.kr/learn/courses/30/lessons/42746
문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한 사항
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
입출력 예
numbersreturn
| [6, 10, 2] | "6210" |
| [3, 30, 34, 5, 9] | "9534330" |
가장 큰 수를 조합해서 출력하는 문제이다.
여기서 핵심은 가장 큰 수를 어떻게 조합하느냐 이다.
생각한 방식은 2가지였다.
1. 일일히 다만들고 리턴하기.
-그러나 이방식은 문제에서 숫자가 너무 커질 수 있다는 것으로 봐서는 불가능하다.
2. 1,10,100,1000만 빼고 내림차순하고 1,10들을 오름차순해서 붙이기
-테스트 케이스 2번을 못보고 결론 내려서 이방법도 아니었다.
그래서 그다음방식으로 생각한건 모두 문자열로 바꾸고 첫째자리 수부터 기준으로 정렬하는 것이었다.
여기서 해결해야할 부분은 자리수가 다른데 어떻게 크기를 비교하냐였다.
이걸 해결하려면 인덱스별로 자리수마다 다르게 비교해야한다.
예를 들어 '3'과 '34'를 비교하면 0번째인덱스는 같지만 한쪽은 1번째인덱스가 없다. 그래서 0번째와 1번째를 비교해야 되는데 이부분에서 막혔다.
참고:https://hocheon.tistory.com/48
이것을
lambda x : x*3으로 해결했다.
같은문자를 3번 곱하는건데 이렇게 되면 자리수가 1개면 계속 그문자로 비교할 수 있다. 즉, 0번째와 1번째 인덱스비교가 사실상 가능해진다.
그리고 마지막에 int로 한번 변환하는 이유는 0000이라는 예외 때문이었다.
역시 모든 수를 조합하는 방식이 아닌 정렬로서 풀어낸 방식이 인상깊었다.
풀이
def solution(numbers):
numbers=list(map(str,numbers))
numbers.sort(key=lambda x:x*3, reverse=True)
return str(int(''.join(numbers)))
n=[3, 30, 34, 5, 9]
print(solution(n))
