큰 수 만들기

• 프로그래머즈의 가장 큰 수 과 동일한 문제이다.
• 하지만 프로그래머즈에서는 레벨2로 책정되어 있는 반면, BOJ에서는 플래티넘으로 책정되어있다. 투표 내역에는 무려 다이아몬드로 투표를 한 의견도 있다.
  • 이 문제를 살짝 응용시킨 문제로 숫자의 신와 Secret Sharing도 있다.
• 숫자들의 자리수가 모두 동일할 경우, 가장 큰 수가 앞에 오도록 정렬시켜서 이어붙이면 된다는 것은 자명하다.
• 숫자들의 자리수가 다르더라도, 어떤 숫자가 다른 숫자의 prefix가 아니라면 그냥 문자열로 취급해서 사전순으로 큰 것을 앞에 오도록 정렬하면 된다.
• 어떤 숫자가 다른 숫자의 prefix가 되는 경우는 조금 복잡하다. 기본적으로는 A와 AB라는 수가 있다면, prefix인 A와 prefix부분을 제외한 B를 비교해서 처리해야 한다. A를 prefix로 갖지 않는 수들은 이미 사전순 정렬에서 비교가 되므로 신경쓸 필요가 없다. 다만 A, AAB와 같은 경우라던가 A,AB,ABC 처럼 있는 경우 등을 모두 다 처리할수 있게 하는 것은 그렇게 간단하지 않다.
• 가능한 해결방법은 숫자 두개를 비교할때 자리수를 맞춰서 비교하는 것이다. 자리수가 짧은 쪽을 반복해서 이어붙여서 길이를 늘려준 후에 비교한다. AB와 ABABC를 비교한다면 ABABA와 ABABC를 비교하는 것으로 바꿔서 처리할 수 있다. 그냥 모든 숫자를 다 최대자리수 이상으로 늘려놓은 것을 키로 삼아서 비교해도 된다. 프로그래머즈의 가장 큰 수에서는 자리수가 최대 4자리 이하여서 이 방법이 편리해서 이런방식으로 풀었다. 코드는 링크 참고.
• 다른 방법은, 두 숫자 X,Y를 XY와 YX로 각각 합쳐보고 그중에서 큰 쪽이 되도록 택하는 방법이다. 이렇게 해도 prefix관계가 아닐때는 사전식 정렬과 동일하게 처리되고, prefix관계일때에도 원하는 대로 처리가 된다. 여기에서는 이 방식으로 풀었다
• 두가지 방법 모두 아이디어를 떠올리는 것은 그렇게 어렵지 않지만, 이렇게 떠올린 비교 기준이 정말로 transitivity를 만족하는지를 증명하는 것은 쉽지 않다. 그것이 프로그래머스와는 달리 BOJ에서 높은 난이도가 책정된 이유이다.
• 최대 자릿수가 m이라고 하면, 비교 연산은 O(m)이다. 따라서 n개의 수를 문자열로 취급해서 정렬하는 데에는 O(mnlogn).

"""Solution code for "BOJ 16496. 큰 수 만들기".

- Problem link: https://www.acmicpc.net/problem/16496
- Solution link: http://www.teferi.net/ps/problems/boj/16496
"""

import functools


def main():
    N = int(input())
    nums = input().split()
    
    nums.sort(key=functools.cmp_to_key(lambda x, y: int(x + y) - int(y + x)), 
              reverse=True)
    answer = ''.join(nums).lstrip('0')
    print(answer or '0')


if __name__ == '__main__':
    main()