문제
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한 사항
•
numbers의 길이는 1 이상 100,000 이하입니다.
•
numbers의 원소는 0 이상 1,000 이하입니다.
•
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
입출력 예시
정답
def solution(numbers):
string_numbers = list(map(str, numbers)) # 문자열로 변환
sorted_numbers = sorted(string_numbers, key = lambda x: x*3, reverse = True) #numbers의 원소는 1,000 이하이므로 3을 곱해서 비교 가능
return str(int(''.join(sorted_numbers))) # int로 변환해주고 다시 string으로 하는 이유 -> [0,0,0,0] 이런 경우 '0' 으로 나와야함
Python
복사
풀이
•
제한 사항을 이용한 풀이이다.
•
먼저 numbers를 문제에 맞게 큰 순서대로 정렬하고 이를 전부 join해서 출력하면 된다.
•
그럼 우리가 찾아야 하는 것은 대소를 정의하는 방식이다.
•
문제에서 정의하는 방식은 우선 문자열의 숫자 비교 방식을 따른다.
•
문자열에서 숫자를 비교하는 방식은 우선 더 짧은 것을 기준으로 문자열을 자른 다음 두 숫자의 대소를 비교하고 만약 잘랐을 때의 두 숫자의 대소가 같다면 길이가 더 긴 것을 더 큰 숫자로 간주한다.
•
따라서 우선 numbers의 원소들을 문자열로 변환한다.
string_numbers = list(map(str, numbers)) # 문자열로 변환
Python
복사
•
그 다음 중요한 것이 우리는 단순히 문자열 비교 방식으로 대소를 비교하면 안 된다는 것이다.
•
예를 들어 원래 문자열 비교에서 ‘3’과 ‘30’ 중에 더 작은 것은 ‘3’이다. 하지만 우리는 문자열을 이어붙일 것이기 때문에 ‘3’이 더 유리하다는 것을 안다. 왜냐하면 ‘30’을 더 먼저 붙여버리면 3의 다음 자리가 0으로 고정되지만 3을 먼저 붙여버리면 다음에 더 큰 것을 붙일 수 있기 때문이다.
다시 예를 들어 ‘3’과 ‘30’ 둘만 있으면 ‘330’이 ‘303’보다 크다.
사실 이러한 문제는 앞자리가 같은 숫자들끼리만 일어나는 문제이다. 앞자리가 다르다면 그대로 문자열을 잘라서 비교하면 된다.
따라서 앞자리가 같은 숫자들끼리 저런 문제가 발생할 때 처리해야 하는데, 이때 3을 곱해주면 문제가 해결된다.
엄밀히 말하면 두 숫자의 대소를 비교할 때 문자열을 잘라서 비교했을 때 같다면 길이가 더 긴 것의 나머지 부분을 앞에서부터 살펴보면서 첫째 자리수보다 크다면 더 큰 것으로 간주하고 첫째 자리수보다 작거나 같으면 그 다음 자리수를 살펴봐야 한다.
예를 들어서
‘3332’와 ‘333235’를 비교해보자.
이때 3332까지는 같으므로 길이가 더 긴 ‘333235’의 나머지 부분(’35’)을 살펴본다. 3은 첫 째 자리 숫자인 3과 동일하므로 그 다음 숫자를 본다. 5는 3보다 크다. 따라서 ‘333235’는 ‘3332’보다 크다.
그런데 이런 방식은 너무 오래 걸린다. 따라서 ‘3332’가 ‘333235’와 길이가 같아지도록 뒤에 첫 째 자리 수인 3을 덧붙이면 간단하게 대소 비교를 할 수 있다.
그런데 최대 자릿수가 3자리로 정해져있다면 우리는 그냥 문자열에 3을 곱해서 비교하면 된다.
왜냐하면 만약 자릿수가 1이라면 자동적으로 뒤에 첫째 자릿수 숫자가 두 개 붙고 자릿수가 2개인 경우 셋 째 자리에 첫째 자릿수 숫자가 붙는다.
예를 들어 ‘3’은 ‘333’이 되고 ‘32’는 ‘323232’가 되는데 ‘323232’의 셋 째 자리 수는 첫 째 자릿수인 3이 된다. 자릿수가 3인 경우에 뒤에 더 붙긴 하는데 사실 문자열의 비교이기 때문에 셋 째 자릿수 이후는 비교가 딱히 무의미해지기 때문에 고려하지 않아도 된다.
따라서 이 방식을 사용해서 ‘3’, ‘30’, ‘34’를 비교하면
‘333’, ‘303030’, ‘343434’를 비교하는데,
‘343434’ > ‘333’ > ‘303030’ 순이다.
sorted 함수의 lambda를 사용해서 이를 구현하자.
sorted_numbers = sorted(string_numbers, key = lambda x: x*3, reverse = True) #numbers의 원소는 1,000 이하이므로 3을 곱해서 비교 가능
Python
복사
→ sorted는 오름차순이므로 reverse를 해줘야 함.
•
마지막으로 join을 사용하여 원소들을 붙여주고 int로 변환하고 다시 string으로 변환해서 출력한다.
•
int로 변경하는 이유는 [’0’, ‘0’, ‘0’, ‘0’] 과 같은 케이스가 ‘0’이 아니라 ‘0000’으로 출력되기 때문.
return str(int(''.join(sorted_numbers))) # int로 변환해주고 다시 string으로 하는 이유 -> [0,0,0,0] 이런 경우 '0' 으로 나와야함
Python
복사