JAVA 자료구조 (배열) 2 - 빗물 트래핑

빗물 트래핑

 

풀이 1- 투 포인터를 최대로 이동

 

 

이 문제는 높이와 너비 모든 공간을 차례대로 살펴 보면 O(n²)에 풀이가 가능하다. 그러나 시간 복잡도가 너무 높기 때문에 좀 더 효율적인 풀이를 찾아야 한다. 투 포인터나 스택으로 O(n) 풀이가 가능할 것 같다. 

 

그림 7-5 투 포인터가 최대를 향해 이동하는 풀이

 

그림 7-5에서 가장 높이가 높은 막대를 한번 살펴보자 위 그림에서는 최대 높이는 3인 곳이 가장 높은 막대이지만 최대 높이가  100이어도 관계는 없다.  막대는 높고 낮음에 무관하게, 전체 부피에 영향을 끼치지 않으면서 그저 왼쪽과 오른쪽을 가르는 장벽 역할을 한다. 

 

volume += leftMax - height[left];

...

volume += rightMax - height[rigth]

 

전체 중에 최대 높이 3을 기점으로 왼쪽 막대 중에 제일 큰 (leftMax -현재 높이)를 계산하면 해당 영역에 몇 블록의 물이 있는지 알수 있고 물이 있는 만큼의 숫자를 volume이라는 변수에 계속 넣어준다.

 

최대 높이의 막대 까지 각각 좌우 막대 최대 높이 leftMax, rightMax가 현재 높이와의 차이 만큼 물 높이 volume을 더해 나간다.

 

if(leftMax <= rightMax){
    volume += leftMax - height[left];
    left +=1;
}else{
    volume += rightMax - height[right];
    right -=1;
}

 

왼쪽포인터와 오른쪽 포인터 모두 낮은 쪽에서 최대 높이 쪽으로 포인터가 하나씩 이동한다.  오른쪽이 높다면  left += 1로 왼쪽 포인터가 이동하고, 반대라면  right -=1로 오른쪽 포인터가 이동한다. 이렇게 하면 그림 7-5가장 높은 막대, 즉 '최대 ' 지점에서 좌우 포인터가 서로 만나게 되면 O(n)에 풀이가 가능하다.

 

💡 tip) Java의 Math.max() 함수

Math.max()함수는 두개의 인자 중 더 큰 값을 반환한다.

 

public int solution(int [] height) {
    int left = 0;
    int leftMax = height[left];

    int right = height.length - 1;
    int rightMax = height[right];

    int volume = 0;

    while (left != right){

        //leftMax와 rightMax가 여기 있어야 하는 이유는
        // 1.left 혹은 right 포인터의 위치를 옮긴 이후에
        // 각각의 위치를 갱신해주어 야 한다.
        leftMax = Math.max(leftMax,height[left]);
        rightMax = Math.max(rightMax,height[right]);

        rightMax = height[right] > rightMax ? height[right] : rightMax;

        if(leftMax <= rightMax){
            volume += leftMax - height[left];
            left +=1;
        }else{
            volume += rightMax - height[right];
            right -=1;
        }
    }

   return volume;
}

 

 

 

[출처 - 자바 알고리즘 인터뷰 with 코틀린 , 저 박상길]

https://www.onlybook.co.kr/entry/java-algorithm-interview

자바 알고리즘 인터뷰 with 코틀린