문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

풀이

원하는 값을 얻기위해선

1. 배열의 두 수를 비교해서 각 숫자를 어떤 순서로 연결할지 결정해야 한다.
2. 숫자의 순서를 정하는 방법은 두 수의 크기뿐 아니라 길이(자릿수)를 통해 비교해야 한다.
3. 제한사항에서 numbers의 원소는 1,000 이하이므로 연산에 소요되는 시간은 크게 중요하지 않다.

처음에는 숫자들의 연결 순서를 정하기 위해 최적의 알고리즘을 생각하려했다.

먼저, 두 수의 자릿수를 비교한다. 만약 [403, 40] 으로 만들 수 있는 순서는 40340, 40403이다. 이때 40을 결정하는 알고리즘은 다음과 같다.

1. 각 원소의 자릿수를 계산 한 후, 둘 중 작은 자릿수의 값을 기억한다. 40의 자릿수 ‘2’
2. 두 수를 작은 자릿수(2) 자리만큼만 비교한다. [40]3 과 [40]
3. 비교한 수가 같은경우 남은 자릿수(1)만큼 비교한다. 40[3] 과 [4]0
4. 해당 자릿수의 값이 높은 원소가 우선순서로 결과 문자열에 연결된다.

하지만 채점을 했더니 몇가지 부분에서 실패를 해서 당황을 했는데, 사실 이 문제는 이렇게 복잡하게 접근할 필요가 없었다.. 두 원소로 만들 수 있는 문자열은 두가지 경우 뿐이므로 두가지 경우를 비교하여 정렬하면 되는 간단한 문제였다.

나는 built-in 함수인 sorted를 응용해보았다. sorted는 객체를 정렬할 때 매우 간편한데 이는 클래스에서 __lt__, __gt__ 등과 같이 비교연산을 하는 대소함수를 만들어주어 쉽게 구현이 가능하다.

코드(Python)

class Number:
    def __init__(self, n):
        self.number = n

    def __lt__(self, other):
        return int(str(self.number)+str(other.number)) > int(str(other.number)+str(self.number))

def solution(numbers):
    answer = ''
    number_list = []
    for number in numbers:
        number_list.append(Number(number))
    number_list = sorted(number_list)
    for a in number_list:
        answer += str(a.number)
    return answer if int(answer) > 0 else '0'

[추가] 코드(Java)

import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Arrays;
import java.util.stream.Collectors;

class Solution {
    public String solution(int[] numbers) {
        Arrays.sort(numbers);
        List<Integer> i_list = Arrays.asList(Arrays.stream(numbers).boxed().toArray(Integer[]::new));

        Collections.sort(i_list, new Comparator<Integer>() {
            public int compare(Integer i, Integer j) {
                return (Integer.parseInt(i.toString() + j.toString()) < Integer.parseInt(j.toString() + i.toString()))
                        ? 1
                        : -1;
            }
        });
        return (i_list.stream().reduce((a, b) -> a + b).get() > 0)
                ? i_list.stream().map(Object::toString).collect(Collectors.joining())
                : "0";
    }
}

자바로도 알고리즘을 구현해보았는데, Comparator를 이용한 정렬을 수행하였다.

if (condition) ? value1 : value2; 와 같은 구조로 코드를 간결하게 표현할 수 있었다.