C# Coding Test Course, Calculating the Amount of Water

Problem Description

There is a tank that can hold water in a specific area. Each wall of the tank has a different height. When it rains, water will accumulate, and the problem is to determine how much water can be held between each wall.

Input

The first line contains an integer N (1 ≤ N ≤ 100,000). N represents the number of walls.
The second line contains N integers h_i (1 ≤ h_i ≤ 1,000,000), which represent the height of each wall.

Output

Print the amount of water that can be held on one line.

Example Problem

Problem Solving Process

To solve this problem, we will use two arrays. One will store the maximum height of walls to the left of the current position, and the other will store the maximum height of walls to the right.

1. Problem Analysis

The amount of water that can be held at each position is the difference between the minimum of the maximum heights of the walls on the left and right, and the current wall height.
For example, the amount of water at position i can be calculated as follows:
water[i] = max(0, min(left_max[i], right_max[i]) - height[i])
where left_max represents the maximum height of walls to the left of i, and right_max represents the maximum height of walls to the right.

2. Algorithm Design

We can design the algorithm in the following steps:

1. Receive the input.
2. Create an array left_max to store the maximum heights of the left walls.
3. Create an array right_max to store the maximum heights of the right walls.
4. Calculate the amount of water that can be held at each position.
5. Finally, output the total amount of water.

3. Code Implementation

Below is the code that implements the above algorithm in C#.

using System;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int[] height = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        // Left maximum height array
        int[] left_max = new int[N];
        left_max[0] = height[0];

        for (int i = 1; i < N; i++)
        {
            left_max[i] = Math.Max(left_max[i - 1], height[i]);
        }

        // Right maximum height array
        int[] right_max = new int[N];
        right_max[N - 1] = height[N - 1];

        for (int i = N - 2; i >= 0; i--)
        {
            right_max[i] = Math.Max(right_max[i + 1], height[i]);
        }

        // Calculate the amount of water
        int water = 0;
        for (int i = 0; i < N; i++)
        {
            water += Math.Max(0, Math.Min(left_max[i], right_max[i]) - height[i]);
        }

        Console.WriteLine(water);
    }
}
    

4. Code Explanation

The algorithm used in the above C# code is as follows:

• int N = int.Parse(Console.ReadLine());
  – Takes the input for N and stores the number of walls.
• int[] height = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
  – Takes the height input and converts it into an array.
• left_max array stores the maximum height from the left. To do this, after setting the height of the first wall, a loop is run to compare the height of each wall and store the maximum value.
• right_max array does the same to store the maximum height from the right.
• Finally, the amount of water that can be held at each wall position is calculated to find the total amount of water.

5. Complexity Analysis

The time complexity of this algorithm is O(N). It performs operations proportional to the number of walls N, so it operates efficiently within the provided input range. The space complexity is also O(N) as it needs space to store the two arrays.

Conclusion

In this article, we solved the problem of calculating the amount of water using C#. Through the process of designing and implementing the algorithm step by step, we were able to confirm problem types that are frequently encountered in coding tests.
I hope this lecture helps you in your preparation for coding tests.