문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한 사항
numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
풀이 00 (실패한 풀이)
from itertools import permutations
def solution(numbers):
# 가능한 순열 조합 찾기
permutation_num = list(permutations(numbers, len(numbers)))
# 각 순열을 문자열로 변환하여 숫자를 이어 붙임
concat_num = [''.join(map(str, perm)) for perm in permutation_num]
# 큰 숫자 찾기
large_num = max(concat_num, key=lambda x: int(x))
return large_num 가장 큰 수를 구하기 위해 가능한 조합을 생각할 수 있는 방법을 찾고자 했다.
- itertools를 활용한 순열, 조합 구현
-
순열 (Permutations) : permutations(반복 가능한 객체, r)
- 반복 가능한 객체(= 길이가 n)에 대해서 중복을 허용하지 않고 r개를 뽑아서 나열
- 뽑힌 순서대로 나열하기 때문에 순서에 의미 O (같은 값이 뽑히더라도 순서가 다르면 다른 경우의 수)
from itertools import permutations for i in permutations([1,2,3,4], 2): print(i, end=" ") >>> (1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3) -
조합 (Combinations) : combinations(반복 가능한 객체, r)
-
반복 가능한 객체(=길이가 n)에 대해서 중복을 허용하지 않고 r개를 뽑음
-
어떤 값을 뽑는지 중요하며, 순서는 고려하지 않음
from itertools import combinations for i in combinations([1,2,3,4], 2): print(i, end=" ") >>> (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)
-
-
위 풀이는 시간 초과가 발생했고, 실패한 풀이로 볼 수 있다.
시간 초과가 발생한 이유로는 위 코드의 경우, 모든 가능한 순열을 생성하고 결과를 처리하는 데 많은 계산량이 필요했기 때문이다.
permutations(numbers, len(numbers))는 숫자의 개수가 n일 때, 총 n!(팩토리얼)개의 순열을 생성한다. 따라서 숫자가 커질수록 순열의 수가 기하급수적으로 증가하며, 이를 메모리에 저장하고 처리하는 데 시간이 오래 걸린다. (* 시간복잡도는 O(n!))
또한, 순열을 생성한 후 각 순열을 문자열로 변환하여 다시 정수로 비교하는 과정에서 연산 비용이 추가로 발생한다. 이는 숫자 개수가 많을수록 비효율적인 계산으로 보여진다.
따라서, 아래 풀이 01부터는 모든 순열을 생성하지 않고 가장 큰 수를 찾는 방법으로 해결해 보고자 한다.
핵심은 문자열 비교 기반 정렬!
풀이 01
def solution(numbers):
# 숫자를 문자열로 변환
str_numbers = [str(num) for num in numbers]
# 정렬 기준: 문자열을 3번 반복한 값을 기준으로 내림차순 정렬
str_numbers.sort(key=lambda num: num*3, reverse=True)
# 정렬 결과 이어붙임
largest_number= ''.join(str_numbers)
# 모든 값이 0인 경우 처리
return '0' if largest_number[0] == '0' else largest_number정렬 기준을 설정하기 위해 숫자를 문자열로 변환을 한다. 이후, 숫자가 아닌 문자열 비교를 하며 문자열 결합(x+y)을 통해 사전순 비교를 수행할 수 있도록 한다.
문자열 정렬 기준은 각 문자열을 3번 반복한 값num*3을 기준으로 내림차순 정렬reverse=True한다.
각 문자열을 최대 3번을 반복하여 충분히 긴 문자열로 만들어 비교를 하여 숫자의 상대적 크기를 정확히 비교하고자 한다.
numbers = [3, 30, 34, 5, 9]
문자열 변환 후: ["3", "30", "34", "5", "9"]
3번 반복 후:
"3" → "333"
"30" → "303030"
"34" → "343434"
"5" → "555"
"9" → "999"
내림차순 정렬 결과: ["9", "5", "34", "3", "30"]이후, 정렬된 문자열을 이어붙이도록 한다. 또한, 모든 값이 0인 경우를 처리하기 위해 조건을 명시적으로 검사하여 문자열 검사를 효율적으로 처리하도록 한다.
참고
