kotlin coding test course, sorting numbers 2

Problem Description

The goal of this problem is to implement an algorithm that sorts given numbers in ascending order. Before outputting the sorted result, read the integers provided as input, remove any duplicate integers, and then output only the sorted result.

Problem Input

            The first line contains the number of integers N. (1 ≤ N ≤ 1,000,000)
            The second line contains N integers, which will be between -1,000,000 and 1,000,000.

Problem Output

            Output the sorted numbers, one per line in increasing order. Duplicate numbers should be output only once.

Example

            Input:
            5
            5
            5
            3
            2
            1

            Output:
            1
            2
            3
            5

Problem Solving Process

To solve this problem, follow these steps:

  1. Input Acquisition: Accept the number of integers N and the N integers entered by the user.
  2. Duplicate Removal: Remove any duplicate integers from the input.
  3. Sorting: Sort the remaining integers in ascending order.
  4. Output: Implement a function to output the sorted numbers.

I will provide code examples for each step in Kotlin below.

Code Implementation

            
            fun main() {
                // Read the number of integers N from the first line.
                val n = readLine()!!.toInt()
                // Read N integers from the second line.
                val numbers = mutableSetOf() // Use Set to avoid duplicates

                // Read N integers and remove duplicates
                for (i in 1..n) {
                    numbers.add(readLine()!!.toInt())
                }

                // Convert to List and sort
                val sortedNumbers = numbers.toList().sorted()

                // Output the sorted result
                for (num in sortedNumbers) {
                    println(num)
                }
            }

This code works as follows:

  • It first takes the number of integers N from the user. Then, through N repetitions, it accepts the integers.
  • Each integer is added to mutableSetOf, which naturally removes duplicates.
  • This is converted to a List using the toList() method, and sorted using sorted().
  • Finally, the sorted results are printed.

Time Complexity Analysis

Analyzing the time complexity of this problem:

  • The process of reading the integers takes O(N), and using a Set for checking duplicates takes O(1) on average.
  • Transforming all elements of the Set to a List and sorting takes O(M log M), where M is the number of unique numbers.
  • Consequently, the time complexity is O(N + M log M).

Conclusion

In this lesson, we reviewed basic data structures and sorting algorithms in Kotlin through the problem of sorting numbers. Kotlin has strengths in utilizing Sets and Lists, and using these effectively can simplify many problems. The next lesson will cover more complex algorithm problems, so please look forward to it.