예제로 배우는 알고리즘 - 투 포인터

 

투 포인터 기본 개념

 

투 포인터 : 두 개의 포인터를 사용하여 배열을 탐색하는 알고리즘

포인터 : 데이터가 저장된 메모리 주소를 가리키는 변수

 

예제 1 - LeetCode 125. Vaild Palindrome

https://leetcode.com/problems/valid-palindrome/description/?envType=study-plan-v2&envId=top-interview-150

 

1개의 포인터는 반복문에서 많이 사용했을 것입니다

String s = "race a car";

for (int i = 0; i < s.length(); i++) {
	s.charAt(i);
}

 

 

거꾸로 읽어도 원래의 문자열과 동일한 회문은 투 포인터를 활용하면 쉽게 해결할 수 있습니다

* 문자열은 문자형의 배열

 

앞에서 읽어도 뒤에서 읽어도 같아야 하기 때문에 left는 1씩 증가하고, right는 1씩 감소하며 각 문자형이 같은지를 확인하여 유효한 회문인지 알 수 있습니다

언제까지 확인해야 할까요? left < right인 경우까지만 확인하면 됩니다

왜냐하면 left >= right인 부분은 이미 확인을 했기 때문에 중복이기 때문입니다

단, 문제의 조건에 따라 대문자는 소문자로, 글자 혹은 숫자가 아닌 경우는 무시해야 함에 주의합시다

 

해답 코드

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        
        // left >= right인 부분은 이미 확인함
        // left < right 조건이 있으므로 left와 right가 인덱스의 범위를 벗어나지 않음
        while (left < right) {
        	// 글자 혹은 숫자가 아니면 패스
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            
            // 소문자로 바꿔서 비교, 다르면 회문이 아니다!!!
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}

 

예제 2 - LeetCode 392. Is Subsequence

https://leetcode.com/problems/is-subsequence/description/?envType=study-plan-v2&envId=top-interview-150

 

임의의 수열에서 일부를 제외해서 얻을 수 있는 부분수열도 투 포인터를 통해 쉽게 해결할 수 있습니다

투 포인터는 회문에서와 같이 한 개의 배열에서 사용할 수도 있고 두 개의 배열에서 활용할 수 있습니다

 

 

t문자열은 1씩 계속 증가시키고, s문자열은 t문자열에서 일치하는 값을 발견할 때마다 1씩 증가시킵니다

그 결과, sIdx가 문자열의 크기(배열의 끝 인덱스 + 1)만큼 도달 했다면 부분 수열이라는 의미입니다

단, 포인터가 인덱스 범위를 벗어나지 않도록 주의해 줍시다

 

해답 코드

class Solution {
    public boolean isSubsequence(String s, String t) {
        int sIdx = 0, tIdx = 0;
		
        // 포인터가 인덱스 범위를 넘어가지 않도록 주의
        while (sIdx < s.length() && tIdx < t.length()) {
        	// t문자열에서 일치하는 값 발견
            if (s.charAt(sIdx) == t.charAt(tIdx)) {
                sIdx++;
            }
            tIdx++;
        }

        return sIdx == s.length();
    }
}

 

이 방법은 s문자열이 하나만 주어질 때는 효과적이지만 많은 s문자열이 주어진다면 비효율적입니다

이 때의 풀이는 투포인터가 아니므로 아이디어만 제시하고 다음 문제로 넘어갈테니 직접 해결해 봅시다

아이디어 : 해시맵에 문자 위치 저장 + 이분 탐색

 

투포인터로 최적해 찾기 - 정렬된 배열

 

예제 3 - LeetCode 167. Two Sum Ⅱ - Input Array Is Sorted

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/?envType=study-plan-v2&envId=top-interview-150

 

배열에서 두 수의 합을 계산하는 가장 쉬운 방법은 이중 for문을 사용하는 것입니다

int[] arr = new int[]{2, 7, 11, 15};

for (int i = 0; i < arr.length; i++) {
	for (int j = 0; j < arr.length; j++) {
    	if (i == j) continue;
        if (arr[i] + arr[j] == target) {
        	return new int[]{i, j};
        }
    }
}

 

이중 for문의 경우 시간 복잡도는 O(N²)입니다

 

정렬된 배열에서 투포인터를 잘 활용하면 최적화를 통해 O(N)의 시간 복잡도로 해결할 수 있습니다

정렬이 된 정수 배열에서 인덱스가 커질수록 값은 증가하고, 작아질수록 값은 감소합니다

이를 이용해 양쪽 끝에 투 포인터를 두고 합한 값이 증가가 필요하면 왼쪽 인덱스를 1씩 더해주고, 감소가 필요하면 오른쪽 인덱스를 1씩 감소하는 방법으로 최적해를 찾을 수 있습니다

예제1과 마찬가지로 left < right인 경우까지만 확인하면 됩니다

단, 반환 값은 실제 인덱스보다 1이 큼에 주의합시다

이 문제는 항상 정답이 존재하지만, 존재하지 않을 경우는 -1, -1을 반환하도록 해봅시다

*해당 문제는 정렬된 배열이 주어져서 O(N)의 시간복잡도이지만, 정렬이 필요할 경우 시간복잡도는 O(NlogN)이 됩니다

 

해답 코드

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[] {left + 1, right + 1};
            } else if (sum > target) {
                right--;
            } else {
                left++;
            }
        }

        return new int[] {-1, -1};
    }
}

예제 4 - LeetCode 15. 3Sum 

https://leetcode.com/problems/3sum/description/?envType=study-plan-v2&envId=top-interview-150

 

예제 3의 응용 문제로 우선, 배열이 정렬되어 있지 않기에 정렬이 필요합니다

for문을 통해 target(-arr[i]))을 정하고 예제3의 방법으로 2Sum을 구하는 방법으로 해결할 수 있습니다

 

 

3개의 값이 필요하므로, for문은 배열의 길이 - 2까지만 탐색하고 left는 target 인덱스의 다음 인덱스, right는 배열의 끝 인덱스로 투 포인터를 초기화하고 해결하면 됩니다

단, 중복 조합 제거를 위해 현재 인덱스의 값이 이전 인덱스의 값과 동일하다면 넘어가야 함에 주의합시다

 

해답 코드

 class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 정렬 시간 복잡도는 O(NlogN)
        Arrays.sort(nums);
        
        int N = nums.length;
        // 2개의 수가 더 필요하므로 N - 2 이전 까지만 탐색
        for (int i = 0; i < N - 2; i++) {
        	// 배열의 첫번째 요소 중복 확인
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int target = -nums[i];
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    
                    // 배열의 두번째 요소 중복 확인
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    // 배열의 세번째 요소 중복 확인
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    // 양쪽을 좁혀서 다음 조합 탐색
                    left++;
                    right--;
                // 비교 결과에 따라 포인터 이동
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return result;
    }
}

 

투포인터로 최적해 찾기 - 정렬되지 않은 배열

 

예제 5 - LeetCode 11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-interview-150

 

때로는 정렬하지 않더라도 규칙만 찾으면 투 포인터를 활용해 최적해를 찾을 수 있습니다

 

 

어느 쪽 포인터를 움직여야 할까요? 최대 컨테이너의 크기를 구한다는 것을 생각해봅시다

1. 높이가 낮은 쪽의 포인터를 이동 => right - left는 항상 감소, 높이는 최대 Math.min(height[left], height[right])

즉, 항상 이전의 크기보다 작아지므로 고려할 필요가 없습니다

2. 높이가 높은 쪽의 포인터를 이동 => right - left는 항상 감소, 높이는 최대 Math.max(height[left], height[right])

즉, 이전의 크기보다 커질 수 있으므로 고려해야 합니다

따라서, 높이가 낮은 쪽의 포인터만 이동을 하면 됩니다

 

해답 코드

class Solution {
    public int maxArea(int[] height) {
        int res = 0, left = 0, right = height.length - 1;

        while(left < right) {
            int minHeight = Math.min(height[left], height[right]);
            int area = (right - left) * minHeight;
            res = Math.max(res, area);
            // 높이가 낮은 쪽을 이동해야 크기가 커질 가능성이 있다!!!
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }   

        return res;     
    }
}