Bài toán : Big Sorting
Level : Easy

Nhận xét : Một bài toán easy level nhưng tôi thấy thực sự hay. Vì từ bài này tôi đã có thể thiết lập được cách để sắp xếp mảng các số rất lớn.
Tóm tắt bài toán : cho một mảng các chuỗi số có thể chứa các số rất lớn chưa được sắp xếp. Việc của chúng ta đơn giản là sắp xếp lại chuỗi sắp xếp tăng dần.
Solution: Nói là đơn giản nhưng nếu lần đầu đọc thì cũng không đơn giản lắm đâu vì. Ta đều biết kiểu dữ liệu long lớn nhất cũng chỉ có 1.8*10^19. À khoan ở các bài viết trước tôi đã đề cập đến BigInteger trong Java tức là nó có thể chứa các số Big Integer trong bài này. Tất nhiên rồi nhưng nếu bạn làm theo kiểu đó sẽ bị Time Out ngay lập tức nhé :D. Tôi đã thử và fail ngay lập tức 😀 Vì nó còn tốn thêm time convert từ String sang BigInteger. Tóm lại bài này tôi sẽ sắp xếp mảng các số rất lớn bằng String theo đúng hướng bài toán. Và tôi thấy so sánh String này cũng rất thú vị.
Về cơ bản tôi sẽ dùng Arrays.sort() trong Java với custom Comparator tự cài đặt để có thể so sánh chuỗi String với số lớn.
Code tham khảo :

Link Pastebin có highlight syntax: https://pastebin.com/X6Sg7pBd

1. import java.io.*;
2. import java.math.*;
3. import java.security.*;
4. import java.text.*;
5. import java.util.*;
6. import java.util.concurrent.*;
7. import java.util.regex.*;
8.  
9. public class Solution {
10.  
11.     // Complete the bigSorting function below.
12.     static String[] bigSorting(String[] unsorted) {
13.             Arrays.sort(unsorted, new Comparator<String>(){//tạo một Comparator so sánh số String
14.                 @Override
15.                 public int compare(String s1, String s2){
16.                     if(s1.length()!=s2.length()){//nếu độ dài 2 chuỗi length khác nhau trừ đi >0 s1 lớn hơn, <0 s1 nhỏ hơn
17.                         return s1.length()-s2.length();
18.                     }
19.                     for(int i=0;i<s1.length();i++){// độ dài 2 chuỗi bằng nhau so sánh từng Char 1 theo bảng mã Ascii
20.                         if(s1.charAt(i)!=s2.charAt(i))
21.                             return s1.charAt(i)-s2.charAt(i);
22.                     }
23.                     return 0;//nếu 2 chuỗi số bằng nhau
24.                 }
25.             });    
26.         return unsorted;
27.     }
28.  
29.     private static final BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
30. //cách đọc bằng Scanner mặc định sẽ bị Time Out 1 test case. Ta phải sửa đọc bằng BufferedReader sẽ nhanh hơn
31.     public static void main(String[] args) throws IOException {
32.         BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv(“OUTPUT_PATH”)));
33.  
34.         int n = Integer.parseInt(bReader.readLine());
35.  
36.         String[] unsorted = new String[n];
37.  
38.         for (int i = 0; i < n; i++) {
39.             String unsortedItem = bReader.readLine();
40.             unsorted[i] = unsortedItem;
41.         }
42.  
43.         String[] result = bigSorting(unsorted);
44.  
45.         for (int i = 0; i < result.length; i++) {
46.             bufferedWriter.write(result[i]);
47.  
48.             if (i != result.length – 1) {
49.                 bufferedWriter.write(“\n“);
50.             }
51.         }
52.  
53.         bufferedWriter.newLine();
54.  
55.         bufferedWriter.close();
56.  
57.         bReader.close();
58.     }
59. }

Have a nice day everyone ! 😀

Conal Dev