꿀잠

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

더해서 목표 값이 되는 두 점을 찾는 문제이다. 이 때 배열은 정렬되어있다. 문제는 그리 어렵지 않고 단순하게 for문 안에서 합계를 넘어가는 수준까지 순환을 하며 값이 완성되는지 확인해도 된다.
하지만 정렬되어있는 배열이기 때문에 이진 탐색을 사용 하는 것이 효율적이다.

목표 값을 찾기 위해 좌측 포인트를 고정하고, 적절한 우측 포인트 값이 있는지 이진 탐색으로 탐색하여 문제를 통과했다.

public class Solution {  
    public int[] twoSum(int[] numbers, int target) {  
  
        for(int i = 0; i < numbers.length - 1; i++){  
            int find = target - numbers[i];  
            int l = i + 1;  
            int r = numbers.length - 1;  
  
            while(l <= r){  
                int mid = l + (r - l) / 2;  
                int now = numbers[mid];  
                if(now == find){  
                    return new int[]{i + 1, mid + 1};  
                }  
  
                if(now > find){  
                    r = mid - 1;  
                }else{  
                    l = mid + 1;  
                }  
            }  
        }  
  
        return null;  
    }  
}

https://leetcode.com/problems/trapping-rain-water/description/

주어진 높이 배열에 물을 담을 수 있는 양을 체크하는 문제이다. 처음 문제를 보았을 때는 쉽게 풀 수 있을거라 생각했지만 막상 풀이를 시도하니 고려해야 할 문제들이 많았다. 좌우 높이 뿐만 아니라 바닥의 높이도 가변적이다 보니 넓이를 구하기가 쉽지 않았다.

바닥의 높이가 좌표마다 다른 점을 해결하기 위해 좌우 벽과 함께 계산된 바닥도 이동 시켜주는 방식으로 생각해주었다. 좌,우 포인트를 더 높은 곳으로 이동시키며 이미 계산한 벽의 높이 만큼은 바닥을 잘라준다고 생각하여 물의 양을 계산해주는 것을 반복하여 풀었다. 아래는 최종 코드이다.

public class Solution {  
    public int trap(int[] height) {  
  
        int answer = 0;  
        int bottom = 0;  
        int l = 0;  
        int r = height.length - 1;  
  
        while(l < r){  
            int leftHeight = height[l];  
            int rightHeight = height[r];  
            int minHeight = Math.min(leftHeight, rightHeight);  
            for(int i = l; i <= r; i++){  
                int nowHeight = height[i];  
                if(nowHeight < minHeight){  
                    answer += minHeight - Math.max(nowHeight, bottom);  
                }  
            }  
  
            bottom = minHeight;  
            if(leftHeight > rightHeight){  
                while(l < r && height[r] <= rightHeight){  
                    r--;  
                }  
            }else{  
                while(l < r && height[l] <= leftHeight){  
                    l++;  
                }  
            }  
        }  
  
        return answer;  
    }  
}

직접 풀이한 내용 외에도 다른 풀이에서 눈에 보였던 점은 좌우 벽의 최대 높이를 배열로 저장해두고 사용하는 방식이었다. 점을 이동시켜 현재 높이를 구하면서도 현재 높이에서 좌우 높이의 최대 값을 확인하는 방식으로 속도 효율이 좋았다. 해당 코드는 아래와 같다.

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int lmax[] = new int[height.length];   
        int rmax[] = new int[height.length];
        int l_max = height[0];
        for(int i=0;i<n;i++){
            l_max = Math.max(l_max,height[i]);
            lmax[i] = l_max;
        }
        int r_max = height[n-1];
        for(int i=n-1;i>=0;i--){
            r_max = Math.max(r_max,height[i]);
            rmax[i] = r_max;
        }
        int count = 0;
        for(int i=0;i<n;i++){
            count+=(Math.min(lmax[i],rmax[i])-height[i]);
        }
        return count;
    }
}