Задачи
April 11

Задача. Хитрая сортировка

Задача: дан массив натуральных чисел, представленных в виде строк. Вам необходимо вывести максимальное число, ктр можно составить из имеющихся чисел.

Входные данные: arr - строковый массив, элементы ктр - натуральные числа, представленные в виде строк. Размер массива не больше 100.

Вывод: вывести максимально возможное число (либо строкой либо числом), ктр можно составить из имеющихся чисел в заданном массиве.

Пример:

arr = [ "123", "124", "56", "90"]

Answer = "9056124123"

Разбор

Очевидно, что обычной сортировкой по убыванию решить задачу не получится, т.к. например массив ["1", "100", "11"] после сортировки будет след.вида: ["11", "100", "1"]. Но число полученное "склейкой" из этого массива (111001) не будет максимальным, максимальное число из этого массива будет: 111100

Давайте сделаем кастомную сортировку по след.правилу: строка X меньше строки Y тогда и только тогда, когда строка X+Y меньше строки Y+X. ('+' - конкатенация строк). Разумеется, мы учитываем, что строки сортируются по убыванию.

Реализация

Play-test

https://dotnetfiddle.net/BbXdhJ