꿀잠

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;
    }
}

https://leetcode.com/problems/container-with-most-water/description/

배열의 인덱스를 x좌표 값을 y좌표로 물이 들어있는 컨테이너를 만들 때 가장 많은 물 양을 담는 방법을 묻는 문제이다.

두 지점을 선택했을 때 가장 최선의 선택이 되는 경우를 찾는 방법이다.
두 인덱스의 차이는 컨테이너의 너비이며 높이는 두 값 중 더 낮은 값이 된다.

문제를 해결하기 위해 왼쪽 인덱스는 차례대로 증가 시켜 주었으며, 높이의 경우 우측 가장 끝부터 좌측 값보다 높은 경우를 찾아주었다. 좌측 값보다 높다면 사각형의 넓이는 좌측 좌표를 기준으로 최대의 높이인 좌측 높이 값이 될 것이며 우측 끝부터 감소 시키며 순환하기 때문에 너비 또한 좌측 값 기준 최대의 값이기 때문이다. 좌측 값을 끝까지 증가 시키며 순회하면 최선의 값이 나오게 된다.

public class Solution {  
    public int maxArea(int[] height) {  
        int answer = 0;  
        for(int i = 0; i < height.length - 1; i++){  
            for(int j = height.length - 1; j >= i + 1 ; j--){  
                int width = j - i;  
                if(height[i] < height[j]){  
                    answer = Math.max(answer, width * height[i]);  
                    break;  
                }else{  
                    answer = Math.max(answer, width * height[j]);  
                }  
            }  
        }  
  
        return answer;  
    }  
}

https://leetcode.com/problems/3sum/description/

배열의 3 요소를 합쳤을 때 값이 0이 되는 조합을 찾는 문제이다. 이 때 같은 숫자의 조합은 중복되어 처리하지 않는다.

우선 처리한 일은 배열의 정렬이다. 인덱스를 순화하며 값의 변화를 예측하기 위해 정렬해주었다.
정렬이 후에는 조합의 합계를 늘리기 위해선 특정 요소의 인덱스를 올리면 되고 낮추기 위해선 인덱스를 낮추면 된다.

요소를 찾기 위해서는 결국 각 인덱스를 순환해야 한다. 이 때 첫 인덱스를 고정적으로 증가시키며 지정해두고, 합계의 값을 비교하여 두 인덱스를 조절하며 조합을 찾아내었다. 중복 요소를 제거하기 위하여, 인덱스를 조절할 때 이전과 같은 경우 인덱스를 추가로 증감하여 같은 값을 제외시켰다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> threeSum(int[] nums) {  
        int n = nums.length;  
  
        List<List<Integer>> answer = new ArrayList<>();  
        Arrays.sort(nums);  
  
        for(int i = 0; i < n - 2; i++){  
            if(i > 0 && nums[i - 1] == nums[i]) continue;  
  
            int j = i + 1;  
            int k = n - 1;  
            while(j < k){  
                int num1 = nums[i];  
                int num2 = nums[j];  
                int num3 = nums[k];  
                if(num1 + num2 + num3 == 0){  
                    List<Integer> triple = new ArrayList<>();  
                    triple.add(num1);  
                    triple.add(num2);  
                    triple.add(num3);  
                    answer.add(triple);  
                }  
  
                if(num1 + num2 + num3 <= 0){  
                    j++;  
                    while(nums[j] == nums[j - 1] && j < k){  
                        j++;  
                    }  
                }else if(num1 + num2 + num3 > 0){  
                    k--;  
                    while(nums[k] == nums[k + 1] && j < k){  
                        k--;  
                    }  
                }  
            }  
        }  
  
  
        return answer;  
    }

https://leetcode.com/problems/valid-palindrome/description/

문자열의 "palindrome" 이라는 조건을 알려주고 해당 조건에 맞는지 여부를 boolean으로 리턴하는 문제이다.

palindrome의 조건은 다음과 같다.

1. 대문자를 소문자로 바꾼다.
2. non-alphanumeric 문자를 지운다.
3. 1-2 과정을 통해 나온 문자를 앞에서 뒤로, 뒤에서 앞으로 읽을 때 같은 문자열이다

해결한 코드는 아래와 같다.

import java.util.*;
// util 패키지를 임포트 해야 어레이리스트를 사용할 수 있다.

class Solution {

	public boolean isPalindrome(String s) {  
		// 1. 문자열의 소문자 변환  
		s = s.toLowerCase();  
		  
		// 2. non-alphanumeric 문자를 제거, alphanumeric 문자만으로 문자열을 새로 구성하기 위해 StringBuilder를 이용  
		StringBuilder createdSb = new StringBuilder();  
		for(int i = 0; i < s.length(); i++){  
		    char c = s.charAt(i);  
		    if(c >= 'a' && c <= 'z'){  
		        createdSb.append(c);  
		    }  
		    if(c >= '0' && c <= '9'){  
		        createdSb.append(c);  
		    }  
		}  
		  
		// 3. StringBuilder의 reverse() 메서드를 이용하여 boolean 값 체크  
		String newStr = createdSb.toString();  
		String reverseStr = new StringBuilder(newStr).reverse().toString();  
		return newStr.equals(reverseStr);
	}

}

자바의 StringBuilder의 메서드 활용하여 풀었다. 이 문제는 예전에 다른 곳에서 본 기억이 살짝 있다. 당시엔 StringBuilder 클래스를 잘 활용하지 못하고 직접 순회하였었다. 이 문제의 카테고리가 Two Pointers인 이유는 각 문자열를 비교하는 것에 이유가 있다. 하지만 자바의 경우 해당 클래스의 메서드를 활용하면 위와 같이 쉽게 해결 가능하다.