미쳤다👻👻👻👻👻👻
어려웠다. 처음에는 도저히 실마리가 잡히지 않았기 때문에.
처음에는 permutations를 시도했었다. 하지만 통과하지 못했다....👉👈
이유는 효.율.성.
permutations를 사용하면 모든 조합을 먼저 계산해버리기 때문에 효율성에서 나쁜 점수를 받은 것 같았다.
한 2시간 쯤 고민하다가 결국 내 뇌속에서 이 문제를 해결하기 위한 실마리를 짜낼 수 없다는 것을 깨닫고 '정렬' 이라는 키워드로 구글링을 했고, 삽입 정렬이라는 것을 사용해서 풀 수 있었다.
(정렬에 관해서는 나중에 정리 할 필요가 있어 보인다.)
나의 풀이는 다음과 같다.
def solution(numbers):
numbers = list(sorted(map(str ,numbers),reverse = True))
for i in range(1,len(numbers)):
for j in range(i, 0, -1):
x,y=numbers[j],numbers[j-1]
if x+y > y+x:
numbers[j],numbers[j-1] = y,x
else :
break
return str(int(''.join(numbers)))우선 처음 numbers를 한번 sorting한 이유는 아래 코드만으로는 통과하지 못하자 성능을 올리기 위해 삽입한 코드다.
모든 요소를 string으로 바꾼 다음에, string의 비교를 통해 sorting한다.
따라서 왼쪽 값이 높은 string이 왼쪽에 위치하게 된다.
이것은 다른 사람들의 풀이 🤬
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이 풀이는 좋아요를 두 번째로 많이 받은 풀이다.
첫 번째 풀이를 가져오지 않은 이유는 그 코드는 진짜 기~가 막히게 푼 코드긴 하지만 딱 이 문제에만 적용될 수 있었던 풀이처럼 보였기 때문에, 이해만 하고 넘어가도 될 것 같았다.
코드를 해부해보자.🧑⚕️
functools의 method인cmp_to_key
우선 공식 문서에는 old-style의 comparison function을 key function으로 바꿔준다고 한다.
나는 old-style function과 key function의 차이를 지금으로서는 알지 못하지만 분명한 것은 old-style function은 JavaScript의 sort 방식과 같은 방식을 취하고 있다는 것을 알 수 있었다.
즉, comparison function이
+1,0,-1을 리턴하며, 두 인자를 받아 -1을 리턴하게 되면 첫 번째 인자를 낮은 인덱스에 끼워넣는 식이다. 그렇게 모든 경우의 두 쌍을 뽑아 비교를 토대로 정렬하는 '것 처럼' 보인다. (확실하지는 않다.)
따라서 그러한 function을 정의해서 sort 함수에 집어넣으면 JS처럼 코드를 짤 수 있다. (이 문제를 처음 봤을 때, JS로 풀고 싶다는 느낌이 들었던 이유가 이것 때문이었다...)
Boolean끼리의 연산을 이용!
comparing 하는 함수에 boolean끼리 연산을 해서 -1, 0 , 1을 return하게 하는 방식은 JS를 사용 할 때도 요긴하게 사용 할 수 있을 것으로 보인다. 기억하고 싶다... 너란 녀석
