(UVA) Children's Game - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1846

First, I tried to use backtracking to solve this problem. Although this first solution found the correct answer, it exceeded the time limit because the maximum number of entries could be 50. Then, I tried another solution that read all the numbers as strings. The comparison is done by concatenating every two strings as string1string2 and string2string1 and checking which one was greater.


import java.io.*;
import java.util.*;
import java.math.*;

class Main {
    public int compareNumbers(int n1, int n2) {
        if (n1 > n2) {
            return 1;
        }
        else if (n1 < n2) {
            return -1;
        } 
        return 0;
    }
   
    public Comparator<String> numberComparator = new Comparator<String>() {
        public int compare(String s1, String s2) {
            StringBuilder sb1 = new StringBuilder(s1);
            StringBuilder sb2 = new StringBuilder(s2);
            String s1s2 = sb1.append(sb2).toString();
            sb1 = new StringBuilder(s1);
            sb2 = new StringBuilder(s2);
            String s2s1 = sb2.append(sb1).toString();
            BigInteger bi1 = new BigInteger(s1s2, 10);
            BigInteger bi2 = new BigInteger(s2s1, 10);
            return bi1.compareTo(bi2);
        }
    };
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        int numNumbers = sc.nextInt();
        while (numNumbers != 0) {
            String[] numbers = new String[numNumbers];
            for (int i = 0; i < numNumbers; i++) {
                numbers[i] = sc.next();
            }
           
            Arrays.sort(numbers, numberComparator);
           
            for (int i = numNumbers-1; i > 0; i--) {
                System.out.print(numbers[i]);
            }
            System.out.println(numbers[0]);
           
            numNumbers = sc.nextInt();
        }
                                       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}