🍀 가장 큰 수

가장 큰 수는 주어진 배열에 담긴 숫자들을 나열했을 때 가장 큰 수를 찾는 문제이다. 순열을 이용해서 풀면 간단하겠다는 싶었지만 시간초과가 나올 것을 예상했는데 시간초과가 발생했다. 따라서 정렬을 이용했는데 고려해야되는 경우는 3, 31, 32라는 숫자를 받았을 때이다. 이를 문자열로 바꾸어 사전정렬을 하게되면 [32, 31, 3]이 나와 32313이라는 수자를 얻게 되지만, 사실상 가장 큰 수는 33231이다. 한 마디로 두 개의 숫자를 이어붙여서 큰 수를 기준으로 정렬하는 것이 포인트이다. 이를 javascript를 이용하여 정렬하는 것은 어렵지 않았지만, python으로 sorting할 때 두 key를 받아야하는 과정(lambda x, y)에서 인자를 한 개밖에 못 받는다는 에러를 받았는데, 이는 여기에서 from functools import cmp_to_key를 이용하여 해결했다. 아래는 로직이다.

💡 32와 3을 비교
num1 = '323'
num2 = '332'
위의 두 수를 만들어 큰 수부터 정렬(내림차순 정렬) 후 join을 이용하여 답을 도출

1️⃣ Python

from functools import cmp_to_key

def key_function(str_num1, str_num2):
    num1 = int(str_num1 + str_num2)
    num2 = int(str_num2 + str_num1)
    
    return num2 - num1

def solution(numbers):
    str_numbers = map(str, numbers)

    return "0" if sum(numbers) == 0 else "".join(sorted(str_numbers, key=cmp_to_key(key_function))) 

처음에 답을 제출했을 때 TC하나가 통과하지 못 했는데 [0, 0, 0]인 경우에는 "0"이라는 반례를 고려하지 못해서였다. 여기서 custom한 key function을 만들기 위해서 cmp_to_key 함수를 사용하였는데 how to compare two elements in python when sorting라고 구글에 질문하여 여기서 찾을 수 있었다. python3에서는 cmp_to_key함수를 임포트하여 사용하고 python2에서는 lambda x, y와 같이 두 인자를 받는다고 선언하여 사용하면 된다.

2️⃣ Javascript

javascript로는 python에서 푼 방식과 다르게 정렬기준을 사용하였다. 주어진 조건이 숫자의 최대 길이는 4이므로 이를 4를 곱해 slicing하는 전략을 선택하였다. 예를 들어 3, 32라는 숫자가 있다면 3333과 32323232.slice(0, 4) 👉🏻 3232를 비교하면 3이 32보다 큰 숫자가 된다.

function sortKey(a, b) {
    a = String(a).repeat(4).slice(0, 4)
    b = String(b).repeat(4).slice(0, 4)
    
    return b - a;
}

function solution(numbers){
    return numbers.reduce((a, b) => a + b, 0) === 0 ? "0" : numbers.sort(sortKey).join("");    
}

🔥 마치며

스택 오버플로우를 참고하다가 custom한 key function을 만들기 위해 그저 두 개의 인자를 받는다고 선언하면 된다는 글 하나만 보고 난 왜 안 되지???하면서 계속 헤맸었다. 프로그래머스에서 선택한 언어는 python3로 cmp_to_key를 이용하여 해결할 수 있었다. cmp_to_key를 몰랐던 것으로 새로운 것을 알게되어 기쁘면서도 더 공부하고 많이 찾아봐야겠다는 생각이 든다. 처음 부터 숫자 길이에 4를 곱한 후 slicing하는 전략을 떠 올랐다면 cmp_to_key라는 것을 몰랐을 것인데 운이 좋았다고 생각하며 블로그를 마친다.

📚 참고

python3 cmp_to_key