가장 큰 수
레벨2, 정렬
이 문제는 예전에 풀다가 포기한것같았다. 뭔가 풀이가 써있기 한데 되는 코드는 하나도 없고 기억도 안나서.. 바닥부터 다시 풀었다.
1. 문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
문제의 요구사항은, 0보다 크거나 같은 수로 구성된 리스트인 numbers가 주어지고, 이를 무작위로 합쳤을 때 가장 큰 수를 반환하는 것이다.
2. 제한사항
1. numbers의 길이는 1 이상 100,000 이하입니다.
2. numbers의 원소는 0 이상 1,000 이하입니다.
3. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
3. 사고과정 / 나의 풀이
당연히 처음에 읽으면서는 브루트포스로 푸는 문제일 줄 알았습니다. 그런데 읽다보니 제한사항이..?
이론상 최대 자릿수가 40만개가 나오고 10만개짜리 리스트를 전부 조합하며 정렬하는건 정신나간 짓 인것 같아서 순수 정렬로만 풀어보았습니다.
def solution(numbers):
numbers = sorted(numbers,
key = lambda x: (str(x)[0],
str(x)[1:2] if str(x)[1:2] else str(x)[0],
str(x)[2:3] if str(x)[2:3] else str(x)[0],
str(x)[2:3] if str(x)[2:3] else str(x)[1:2],
-len(str(x))
),
reverse=True)
answer = ''.join(list(map(str, numbers)))
answer = '0' if answer[0] == '0' else answer
return answer
처음 생각한 풀이는 크게 어렵지 않을것같았습니다. 자릿수가 크되, 맨 앞자리를 구성하고있는 숫자가 크면 장땡 아닌가..? 라는 생각으로 lambda에서 세번째 라인까지만 썼습니다. 그나마도 인덱스로 처리하려다가 자꾸 에러를 뱉길래 꼼수로 인덱스로 처리해버렸습니다.
그런데 전체 리스트를 찍어보니 예외가 되는 경우가 다소 보였습니다. 989, 987과 98의 경우 등을 잘 처리하지 못했습니다. 따라서 세번째 자리까지 비교를 위해 네번째 조건을 넣어주었습니다.
풀면서 참.. 다른 함수를 만들어서 써야할것같은 충동을 계속 누르면서 이 악물고 어떻게든 파이썬 기본정렬로 승부를 보고자 했습니다.
사실 len기준도 앞에 따로 빼놨다가, sorted 에서 키 3개 넘어가는순간 에라모르겠다 하고 넣어버렸는데, 훨씬 보기 좋아진것같아서 놀랐습니다..
그런데 이렇게 제출해보니 테스트케이스 11만 불통... 긴가민가 하다가 조건에 0이상.. 을 보고 혹시나 싶어서 마지막에서 두번째 줄 코드를 추가했습니다. 목적은 정렬 후, 맨 앞이 0인 경우, 즉 모든 수가 0인 경우를 예외처리했더니 결국 모든 케이스를 통과했습니다.
이 날엔 차마 다른 풀이를 써보진 못했습니다... ㅠ
그래도 본의아니게 다른 사람들의 풀이보다 확연이 빠른(가장 오래걸리는 테스트케이스 3 기준 약 220ms, 타 코드는 수천ms) 풀이로 풀었다는 점에서 크게 만족감을 얻었고, 다시 한번 파이썬 기본 함수를 만드신 개발자들에 대한 경외심이 솟아올랐습니다.
3. 다른 사람의 풀이
일단 맨 위 풀이 확인이 정석.
def solution3(numbers):
numbers = list(map(str, numbers))
numbers.sort(key=lambda x: x*3, reverse=True)
return str(int(''.join(numbers)))
처음 보고 한 3초 동안 멍하니 보고만 있었다. 이걸 내장함수로 네줄만에 풀다니..? 대체 *3의 의미가 뭘까 계속 생각했다.
처음엔 999*3 = 2997 이런건가 싶어서 내가 모르는 수학적 풀이가 있는건가 한참을 생각했는데, 잘 보니 이미 그전에 스트링으로 바뀌어있었다.
사실 차마 여기까지 생각하기도 전에 *3에서 정신이 나간 상태여서 더 오래 헤멘 것 같다.
그리고 얼마 뒤 정신을 차리고 다시 곰곰히 생각해보니, 대략적인 원리는 이해했지만 왜 그게 하필 3인가에 대해서는 도달하는데에 조금 더 시간이 걸렸다. 잠시 뒤에야 현재 비교해야하는 자릿수가 최대 세자릿수이기에, *3은 되어야 충분히 상호 비교가 가능하다는 것을 깨달았다.
아 물론 1000이 있기는 하지만, 1000의 경우에는 숫자가 반복되어 대소관계가 복잡한 경우가 여기서는 발생하지 않는다.
여기서 말하는 숫자 비교가 복잡해지는 경우는, 9와 998을 들 수 있다. 이런 경우 *2라면 각각 99와 998998이 되기에, 정렬 가
[998998, 99]
가 되어버려 결국 정렬이 [998, 9]가 되어버린다. 즉 9와 998의 세번째 자릿수인 8이 비교되지 않는다.
그렇기에 *3으로 가상의 세번째 자릿수를 만들어주어서 이를 해결한 것이다. 이렇게 되면 키가
[999, 998998998]가 되어 정렬은 우리가 원하는대로 [9, 998]이 된다.
import functools
def comparator(a,b):
t1 = a+b
t2 = b+a
return (int(t1) > int(t2)) - (int(t1) < int(t2)) # t1이 크다면 1 // t2가 크다면 -1 // 같으면 0
def solution(numbers):
n = [str(x) for x in numbers]
n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
answer = str(int(''.join(n)))
return answer
cmp_to_key라는 함수를 처음 봤다. (참고: https://docs.python.org/ko/3/howto/sorting.html)
functools.cmp_to_key()함수로 정렬시 lamba 이외에, 다른 함수를 쓸 수 있게 해주는 특이한 함수였다.
그런데 그럴거면 lambda x, y: (생략) 이나, 그냥 func를 키로 넣으면 안되나? 싶은 생각이 잠깐 들었는데, 이 함수는 정렬되는 리스트의 각 원소를 두개씩 선정하여 비교하는 함수이다.
매우 특이한 경우에 사용되는 함수이긴 하지만, 꼭 필요한 순간에 꽤나 중요하게 써먹을 수 있을 것 같은 함수이니 기억해두기로 했다.
from io import StringIO
def cmp_to_key(mycmp):
'Convert a cmp= function into a key= function'
class K:
def __init__(self, obj, *args):
self.obj = obj
def __lt__(self, other):
return mycmp(self.obj, other.obj) < 0
def __gt__(self, other):
return mycmp(self.obj, other.obj) > 0
def __eq__(self, other):
return mycmp(self.obj, other.obj) == 0
def __le__(self, other):
return mycmp(self.obj, other.obj) <= 0
def __ge__(self, other):
return mycmp(self.obj, other.obj) >= 0
def __ne__(self, other):
return mycmp(self.obj, other.obj) != 0
return K
def comparator(x, y):
x = str(x)
y = str(y)
x_y = int(x + y)
y_x = int(y + x)
if x_y < y_x:
return -1
elif y_x < x_y:
return 1
else:
return 0
def solution(numbers):
numbers = sorted(numbers, key=cmp_to_key(comparator), reverse=True)
string_buffer = StringIO()
for number in numbers:
string_buffer.write(str(number))
answer = int(string_buffer.getvalue())
return str(answer)
아니,, 이분은 cmp_to_key()를 아예 구현해버리셨다.. 할말이 없다..... 대단하다...
def solution(numbers):
nums = [str(n) for n in numbers]
longest = max([len(n) for n in nums], default=0)
nums.sort(key=lambda x: x*(longest//len(x)+1), reverse=True)
return str(int(''.join(nums)))
이분은 맨 처음 코드의 x*3 부분을 하드코딩이 아닌 동적으로 구현하셨다. 자릿수 제한이 없는 경우에 유용할것같다.
