C# 코딩테스트 강좌, 물의 양 구하기

문제 설명

특정 지역에 물을 담을 수 있는 수조가 있습니다. 수조의 각 벽은 높이가 다릅니다. 비가 내리면 물이 담기게 될텐데,
각 벽 사이에 얼마나 많은 물이 담길 수 있는지를 구하는 문제입니다.

입력

첫 번째 줄에는 정수 N(1 ≤ N ≤ 100,000)이 주어집니다. N은 벽의 개수를 나타냅니다.
두 번째 줄에는 N개의 정수 h_i (1 ≤ h_i ≤ 1,000,000)가 주어지며,
이는 각 벽의 높이를 나타냅니다.

출력

한 줄에 물이 담길 수 있는 양을 출력합니다.

문제 예제

예제 입력:
5
0 1 0 2 1 0 1 3 2 1 2 1
예제 출력:
6

문제 풀이 과정

이 문제를 풀기 위해서 우리는 두 개의 배열을 사용할 것입니다.
하나는 현재 위치에서 왼쪽에 있는 벽의 최고 높이를 저장하고, 또 하나는 오른쪽에 있는 벽의 최고 높이를 저장합니다.

1. 문제 분석

각각의 위치에서 담길 수 있는 물의 양은, 그 위치의 벽 높이보다 왼쪽과 오른쪽의 벽 높이 중 최소값에서 현재 벽 높이를 뺀 값입니다.
예를 들어, 위치 i에서 물의 양은 다음과 같이 계산할 수 있습니다:
water[i] = max(0, min(left_max[i], right_max[i]) - height[i])
여기서 left_max는 i의 왼쪽 벽 중 최대 높이를, right_max는 오른쪽 벽 중 최대 높이를 의미합니다.

2. 알고리즘 설계

우리는 다음과 같은 단계로 알고리즘을 설계할 수 있습니다.

  1. 입력을 받아온다.
  2. 왼쪽 벽의 최대 높이를 저장하는 배열 left_max를 생성한다.
  3. 오른쪽 벽의 최대 높이를 저장하는 배열 right_max를 생성한다.
  4. 각 위치에서 담길 수 있는 물의 양을 계산한다.
  5. 최종적으로 물의 총량을 출력한다.

3. 코드 구현

아래는 위의 알고리즘을 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);

        // 왼쪽 최대 높이 배열
        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]);
        }

        // 오른쪽 최대 높이 배열
        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]);
        }

        // 물의 양 계산
        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. 코드 설명

위의 C# 코드에서 사용된 알고리즘은 다음과 같습니다.

  • int N = int.Parse(Console.ReadLine());
    – N값을 입력받아 벽의 개수를 저장합니다.
  • int[] height = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    – 높이 입력을 받아 배열로 변환합니다.
  • left_max 배열은 왼쪽에서부터의 최대 높이를 저장합니다. 이를 위해 첫 번째 벽의 높이를 세팅한 후, 반복문을 돌며
    각 벽의 높이를 비교하여 최대값을 저장합니다.
  • right_max 배열도 마찬가지로 오른쪽에서부터 최대 높이를 저장합니다.
  • 마지막으로, 각 벽 위치에서 물이 담길 수 있는 양을 계산하여 총 물의 양을 구합니다.

5. 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)입니다. 벽의 개수 N에 비례하여 연산을 수행하므로 제공된
입력 범위 내에서 효율적으로 동작합니다. 공간 복잡도 또한 O(N)으로 두 개의 배열을 저장하기 위한 공간이 필요합니다.

결론

이번 글에서는 물의 양을 계산하는 문제를 C#으로 해결해 보았습니다. 알고리즘을 단계적으로 설계하고
구현하는 과정에서 코딩 테스트에서 자주 접할 수 있는 문제 유형들을 확인할 수 있었습니다.
이 강좌가 당신의 코딩 테스트 준비에 도움이 되기를 바랍니다.