이 글에서는 주어진 숫자 목록의 순서를 조합하여 만들 수 있는 가장 큰 숫자를 찾는 방법을 알아봅니다. 문제를 해결하는 두 가지 방법을 단계별로 소개하겠습니다.
방법 1: itertools 순열(permutations) 활용
첫 번째 방법은 모든 순열을 생성한 뒤 그중 최댓값을 찾는 방식입니다. 다음 단계를 따라 해결할 수 있습니다.
- 순열(permutations) 메서드를 사용하기 위해
itertools모듈을 임포트합니다. - 숫자 목록과 결과를 담을 빈 리스트를 초기화합니다.
- 목록의 모든 순열을 순회하면서 각 조합을 문자열로 연결해 결과 리스트에 추가합니다.
max메서드와key=int를 사용해 결과 중 최댓값을 찾습니다.- 문자열을 정수로 변환하여 출력합니다.
예제 코드
# 모듈 임포트
import itertools
# 리스트 초기화
numbers = [45, 35, 138, 43, 67]
# 결과를 담을 리스트
result = []
# 순열 생성
for permutation in itertools.permutations(str(number) for number in numbers):
result.append(''.join(permutation))
# 최댓값 찾기
maximum = max(result, key=int)
# 최댓값 출력
print(int(maximum))위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
출력 결과
67454335138
순열 방식은 직관적이지만, 숫자가 n개일 때 n!개의 조합을 모두 검사해야 하므로 목록이 커지면 실행 시간이 급격히 늘어난다는 단점이 있습니다.
방법 2: sorted 함수와 커스텀 정렬 기준 활용
두 번째 방법은 sorted 함수에 사용자 정의 비교 함수를 적용해 훨씬 효율적으로 문제를 해결하는 방식입니다. 다음 단계로 코드를 작성합니다.
- 숫자 목록을
sorted함수에 전달합니다. - 두 개의 인자를 받는
get_key함수를 작성합니다. str(first) + str(second)가str(second) + str(first)보다 크면-1을, 그렇지 않으면1을 반환합니다.- 정렬된 목록의 요소를
join메서드로 연결합니다. - 결과를 정수로 변환하여 출력합니다.
일반 함수를 정렬 기준으로 사용하려면 functools 모듈의 cmp_to_key 메서드로 변환해야 합니다. 코드를 살펴보겠습니다.
예제 코드
from functools import cmp_to_key
# 리스트 초기화
numbers = [45, 35, 138, 43, 67]
def get_key(first, second):
if str(first) + str(second) > str(second) + str(first):
return -1
return 1
# 정렬로 결과 얻기
result = sorted(numbers, key=cmp_to_key(get_key))
# 결과 연결
result = "".join(str(integer) for integer in result)
# 결과 출력
print(int(result))위 코드를 실행하면 첫 번째 방법과 동일한 결과를 얻을 수 있습니다.
출력 결과
67454335138
정리
두 방법 모두 동일한 결과를 출력하지만, 순열 방식은 시간 복잡도가 O(n!)인 반면 정렬 방식은 O(n log n)으로 훨씬 효율적입니다. 따라서 실무에서는 두 번째 방법을 사용하는 것이 좋습니다. 핵심 아이디어는 두 숫자 a, b를 이어 붙였을 때 ab와 ba 중 어느 쪽이 더 큰지 비교하는 것입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.