자바스크립트 코딩테스트 강좌, 물의 양 구하기

문제 정의

주어진 높이의 막대기 배열이 있을 때, 비가 내렸을 때 모일 수 있는 물의 양을 구하는 문제입니다. 막대기의 높이는 배열의 각 요소로 주어집니다.

예를 들어, 배열이 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]이라면, 모일 수 있는 물의 양은 6입니다. 이 예제에서 각 막대기 사이에 물이 어떻게 저장되는지를 시각적으로 나타내면 다음과 같습니다:

문제를 해결하기 위한 접근법

이 문제를 해결하기 위해 사용할 수 있는 다양한 방법이 있습니다. 가장 흔히 사용되는 두 가지 접근 방법은 다음과 같습니다.

1. 투 포인터(Two Pointers) 방법

   이 방법은 두 개의 포인터를 양쪽에서 중앙으로 이동시키면서 진행합니다. 각 포인터는 왼쪽과 오른쪽에서 높이를 추적하며, 이를 통해 물이 고일 수 있는 위치를 계산합니다.

2. 동적 프로그래밍(Dynamic Programming)

   이 방법은 각 위치에서 왼쪽과 오른쪽에서 가장 높은 막대기를 찾고, 그 중 더 낮은 막대기로부터 물의 양을 계산합니다. 하지만 이 방법은 추가적인 메모리를 많이 사용한다는 단점이 있습니다.

JavaScript로 문제 해결하기

먼저 투 포인터 방법을 사용하여 코드를 작성해 보겠습니다. 우리는 배열의 양 끝에서 시작하여 중앙으로 이동하며 물의 양을 계산하는 알고리즘을 구현합니다.

코드 예제

function trap(height) {
    if (height.length === 0) return 0;

    let left = 0;
    let right = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    let waterTrapped = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                waterTrapped += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                waterTrapped += rightMax - height[right];
            }
            right--;
        }
    }

    return waterTrapped;
}

            

위의 함수는 height 배열을 입력받아 비가 내린 후 모일 수 있는 물의 양을 계산합니다.

코드 설명

위 코드를 단계별로 살펴보겠습니다:

1. 초기화: left는 0으로 초기화하고, right는 배열의 마지막 인덱스(길이 – 1)로 초기화합니다. leftMax와 rightMax는 각각의 방향에서의 최대 높이를 저장합니다. waterTrapped는 최종적으로 저장되는 물의 양을 나타냅니다.
2. 루프 실행: left가 right보다 작을 때까지 루프를 실행합니다. 각 반복에서, 왼쪽과 오른쪽의 높이를 비교하여 더 낮은 쪽에서 물의 양을 계산합니다.
3. 물의 양 계산: 왼쪽의 높이가 더 낮은 경우, 왼쪽의 최대 높이와 현재 높이를 비교하여 물이 저장될 수 있는 양을 계산합니다. 마찬가지로 오른쪽에서 같은 작업을 수행합니다.
4. 결과 반환: 모든 루프가 완료된 후, waterTrapped 변수를 반환하여 최종 결과를 출력합니다.

코드 테스트

이제 우리가 작성한 알고리즘을 테스트해 보겠습니다. 아래와 같은 여러 가지 예제를 통해 함수의 성능을 확인할 수 있습니다:

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
console.log(trap([4, 2, 0, 3, 2, 5])); // 9
console.log(trap([])); // 0
console.log(trap([1, 0, 1])); // 1

            

각 출력값은 예측된 물의 양과 일치해야 합니다. 다음과 같은 결과가 출력됩니다:

• trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) – 6
• trap([4, 2, 0, 3, 2, 5]) – 9
• trap([]) – 0
• trap([1, 0, 1]) – 1

성능 분석

위의 알고리즘은 O(n)의 시간 복잡도를 가지며, O(1)의 공간 복잡도를 갖습니다. 이는 입력 배열의 크기에 비례하여 수행 시간과 공간을 필요로 함을 의미합니다. 따라서 대량의 데이터에 대해서도 효율적으로 동작합니다.

만약 동적 프로그래밍을 사용한다면 높이를 저장하기 위한 추가 배열을 필요로 하므로 공간 복잡도는 O(n)이 됩니다. 그러나 시간 복잡도는 동일하게 O(n)입니다.

결론

이번 강좌에서는 ‘물의 양 구하기’ 문제에 대해 논의하고, 자바스크립트를 사용하여 이를 해결하는 방법을 소개했습니다. 투 포인터 알고리즘을 사용하여 문제를 효율적으로 해결할 수 있었고, 코드의 구현 및 성능 분석 또한 진행했습니다.

이 문제는 다른 알고리즘 문제에 적용할 수 있는 중요한 개념들이 포함되어 있으므로, 다른 유사한 문제도 연습해 보신다면 알고리즘 실력을 더욱 향상시킬 수 있을 것입니다.

이상으로 자바스크립트 코딩테스트 강좌를 마치겠습니다. 여러분의 코딩 실력 향상에 도움이 되기를 바랍니다!