Java Coding Test Course, Queueing

In this lecture, we will cover useful algorithm problems for job preparation using Java. The topic is “Queue Formation,” and through this problem, you can enhance your basic understanding of data structures, sorting, and algorithms and develop skills that can be applied in actual coding tests.

Problem Description

This is a problem of lining up students based on their heights. We want to arrange students with different heights in a line. In other words, when there are N students and their height information is provided, please write a program that sorts them and outputs their heights in order.

Input

• The first line contains the number of students N. (1 ≤ N ≤ 100,000)
• The second line contains each student’s height, separated by spaces. (1 ≤ height ≤ 200)

Output

Output the students’ heights in ascending order.

Example Input

5
170 165 180 175 160
    

Example Output

160 165 170 175 180
    

Problem Solving Process

1. Understanding the Problem

To solve the problem, we first need to clearly understand the requirements. We need to sort the students’ heights provided as input and output them. Considering the possible large input size, it is necessary to choose an efficient sorting algorithm.

2. Algorithm Selection

The number of students can be up to 100,000, and each height value ranges from 1 to 200. In this case, we can use comparison-based sorting algorithms such as Quick Sort and Merge Sort, but given the limited range of heights, it is more efficient to use the Counting Sort algorithm.

3. Explanation of Counting Sort Algorithm

Counting Sort can perform sorting with a time complexity of O(N + k), where k is the range of values of the data being sorted. In this problem, since each student’s height is an integer between 1 and 200, k becomes 200. The Counting Sort process is as follows:

1. Create an array to store the number of times each height appears.
2. Read each input height one by one and increase the corresponding index.
3. Output the sorted values using the count array.

4. Java Code Implementation

Below is the Java code based on the above algorithm:

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Input number of students N
        int N = scanner.nextInt();
        // Declare array to hold the number of heights (1-200)
        int[] heightCount = new int[201];

        // Input heights of students and count them
        for (int i = 0; i < N; i++) {
            int height = scanner.nextInt();
            heightCount[height]++;
        }

        // Output sorted heights
        StringBuilder result = new StringBuilder();
        for (int i = 1; i <= 200; i++) {
            while (heightCount[i] > 0) {
                result.append(i).append(" ");
                heightCount[i]--;
            }
        }
        System.out.println(result.toString().trim());

        scanner.close();
    }
}
    

5. Code Explanation

In the code above, we create a count switch array based on the number of students, counting each student’s height by index. Then, we traverse the count array to output the indices where values exist in the result string.

6. Time Complexity

The time complexity of this algorithm is O(N + k). N is the number of students, and k is the range of heights. Therefore, this algorithm is very efficient and suitable for meeting the constraints of the problem.

Conclusion

In this lecture, we learned how to solve the “Queue Formation” problem using the Counting Sort algorithm. This technique is particularly useful in situations where the range of values is limited or easily predictable. Since you are likely to encounter similar problems in actual coding tests, try to further develop your own algorithm skills!