Secret Sharing

• 큰 수 만들기의 응용 문제이다.
• 큰 수 만들기 에서의 핵심은, 수들을 늘어놓아서 가장 큰 수를 만들기 위해서는 수들을 문자열로 처리해서 정렬하되 비교함수를 x+y<y+x 로 놓으면 된다는 것이다.
• 여기에서도 같은 원리를 쓰면 되지만, 0으로 시작하는 수가 맨 처음에 올 수 없다는 조건에 신경을 써야 한다.
• 0으로 시작하는 수가 x개라면, 수들을 합쳐서 가장 작은수를 만들었을때 0으로 시작하는는 숫자들은, 2번째부터 x+1번째까지 붙어서 나올것이다. 이 수들만 따로 뽑아서 정렬해 놓고, zero_part라고 부르자.
• 0으로 시작하지 않는 수들 중에서는 한개만 zero_part 앞에 배치될 것이고, 나머지는 zero_part 뒤에 올것이다.
• 0으로 시작하지 않는 수들 중에서 zero_part 앞에 올 한개의 숫자를 찾는 것은, x+zero_part+y<y+zero_part+x 의 비교 조건을 이용해서 찾으면 된다.
• zero_part 뒤에 올 수들은 평범하게 x+y<y+x로 정렬하면 된다.
• 결국 이것도 정렬로 풀리는 것은 마찬가지. 시간복잡도는 O(mnlogn)

"""Solution code for "BOJ 2385. Secret Sharing".

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

import functools


def main():
    N = int(input())  # pylint: disable=unused-variable
    shares = input().split()

    comp_key = functools.cmp_to_key(lambda x, y: -1 if (x + y) < (y + x) else 1)
    zero_shares = [x for x in shares if x[0] == '0']
    nonzero_shares = [x for x in shares if x[0] != '0']
    if not nonzero_shares:
        print('INVALID')
        return

    zero_part = ''.join(sorted(zero_shares, key=comp_key))
    z = zero_part[:5]
    first_part = min(
        nonzero_shares,
        key=functools.cmp_to_key(
            lambda x, y: -1 if (x + z + y) < (y + z + x) else 1))
    nonzero_shares.remove(first_part)
    last_part = ''.join(sorted(nonzero_shares, key=comp_key))

    print(first_part + zero_part + last_part)


if __name__ == '__main__':
    main()