문제

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

조건

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예시

입출력	예
numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

통과한 풀이

아이디어

• Array.prototype.sort() 메소드에 단순히 return a - b 말고도 다른 방식으로 활용할 수 있음을 깨닫게 해주는 문제이다.
• 여기서 가장 고민했던 케이스가 3 vs 30과 같은 경우인데, 상당히 획기적인 compareFunc를 작성함으로써 해결할 수 있었다. (그래서 난이도와 다르게 코드 양은 엄청 짧음)
  • 바로 3과 30을 받았을 때, 각각을 문자열로 바꾼 다음 + 연산자를 통해서 concat한 결과끼리 빼서 (303 - 330) 결과에 따라서 3과 30의 순서를 정렬을 하는 것이다!!

🚨주의할 점!!
함정 케이스로 [0, 0, 0, ..., 0]이 들어가있을 수 있다. 그런 경우 따로 처리해주지 않으면 answer에 '00000'과 같은 문자열이 들어갈 수 있으므로 이런 케이스를 따로 처리해주자.

코드

function solution(numbers) {
    var answer = '';
    answer = numbers.sort((next, prev) => {
        return (prev.toString() + next.toString()) - (next.toString() + prev.toString());
    }).join("");
    
    if (answer[0] === '0')
        return '0';
    else return answer;
}

개선할 점

덕지덕지 붙어 있는 Number.prototype.toString()을 없애보자.
이를 위해서는 처음에 numbers를 받았을 때 안에 있는 숫자들을 다 문자로 만들고 그 배열에다가 처리하는 방법이 있겠다.

숫자를 문자로 바꾸는 방법

1. 각 숫자에 Number.prototype.toString() 적용하기
2. String()으로 각각의 숫자를 감싸기
3. 각 숫자에 빈 문자열("") 이어붙이기
4. Template String 이용하기

   const number1 = 123.1;
    const number2 = 123;
    const str1 = `${number1}`;
    const str2 = `${number2}`;

코드

function solution(numbers) {
    var answer = '';
    var num_to_str = numbers.map(num => num + '');
    answer = num_to_str.sort((next, prev) => {
        return (prev + next) - (next + prev);
    }).join("");
    
    if (answer[0] === '0')
        return '0';
    else return answer;
}

파이썬 코드 1

• 파이썬에서는 커스텀 정렬을 functools의 cmp_to_key를 이용하여 구현할 수 있다.
• 양수를 반환하면 순서를 바꿔야 함을 의미하고, 나머지는 순서 유지를 의미한다.

from functools import cmp_to_key

def compare(x, y):
    r1 = x + y
    r2 = y + x
    
    return 1 if int(r1) < int(r2) else -1

def solution(numbers):
    # 우선 다 문자열로 바꿔준다.
    numbers = [str(num) for num in numbers]
    result = sorted(numbers, key=cmp_to_key(compare))
    
    answer = ''.join(result)
    answer = answer if answer[0] != '0' else '0'
    
    return answer

파이썬 코드 2

• 이전의 방법들처럼 앞뒤의 수를 concat해서 정렬하는 방법도 있지만, 각자 본인을 3번 concat해서 대소비교를 하는 방법도 있다. (3번 concat하는 이유는 문제에서 numbers의 각 숫자들은 1000까지라고 했으므로)
• 예를 들어, '300'과 '3'을 비교할 때, '300300300'과 '333'을 문자 순으로 비교하는 것이다. 그렇게 했을 때 reverse한 순서로 정렬해주면 된다. (시간이 진짜 빠르다)

def solution(numbers):
    # 우선 다 문자열로 바꿔준다.
    numbers = [str(num) for num in numbers]
    result = sorted(numbers, key=lambda x: x*3, reverse=True)
    
    answer = ''.join(result)
    answer = answer if answer[0] != '0' else '0'
    
    return answer