C# Coding Test Course, Finding Building Order

Problem Definition

This problem involves a process of stacking buildings in a specified order of heights. Each building has a unique height, which is given as an integer. Our goal is to determine whether it’s possible to stack the buildings in the given order of heights and to output that order.

The specifications for the algorithm to be written are as follows:

• Input: The heights of N buildings are given.
• The buildings must be stacked starting from the shortest to the tallest.
• Output: Display the possible stacking order and whether it can be achieved.

Example

Input

                5
                3
                1
                5
                4
                2
            

Output

                Possible
                1, 2, 3, 4, 5
            

Input

                3
                2
                1
                2
            

Output

                Impossible
            

Problem Solving Process

To solve the problem, the following steps must be carried out.

1. Input Value Collection: Allow the user to input building heights.
2. Sorting: Sort the building heights in ascending order.
3. Duplicate Check: Verify if there are any identical heights. If duplicates exist, it is deemed impossible.
4. Output: Output the stacking order of the buildings and check if it’s possible to inform the user.

C# Code Implementation

Based on the above procedures, I will implement the code in C#. Below is the implemented code.

                using System;
                using System.Linq;

                class Program
                {
                    static void Main(string[] args)
                    {
                        int N = Convert.ToInt32(Console.ReadLine());
                        int[] heights = new int[N];

                        for (int i = 0; i < N; i++)
                        {
                            heights[i] = Convert.ToInt32(Console.ReadLine());
                        }

                        var orderedHeights = heights.Distinct().OrderBy(h => h).ToArray();

                        if (orderedHeights.Length != heights.Length)
                        {
                            Console.WriteLine("Impossible");
                        }
                        else
                        {
                            Console.WriteLine("Possible");
                            Console.WriteLine(string.Join(", ", orderedHeights));
                        }
                    }
                }
            

Code Explanation

Let me explain the key parts of the code.

• Input Value Collection: The Console.ReadLine() method is used to receive user input.
• Duplicate Removal and Sorting: The Distinct() method of LINQ is used to remove duplicates, followed by OrderBy() for sorting in ascending order.
• Validity Check: Compare the lengths of the original and duplicate-removed arrays to check for duplicates.
• Output: Output the possible stacking order or display a message indicating that it is impossible.

Conclusion

Through this tutorial, we learned the process of solving an algorithm problem related to determining the order of buildings. By utilizing arrays and LINQ in C#, we could efficiently perform duplicate checks and sorting. Solving such types of problems can enhance our understanding of various data structures and algorithms. Additionally, practice testing the code against different cases to develop a more robust implementation.