Two pointers 대표 문제 풀기

이번 포스트에서는 Two pointers 기법으로 풀 수 있는 대표 문제를 풀어보도록 하겠습니다!

문제풀이는 C++로 진행하겠습니다.

1. Valid Palindrome

Valid Palindrome - LeetCode

풀이

class Solution {
public:
    bool isPalindrome(string s) {
        
        // 불필요한 문자열을 제거한 최종 결과물을 저장합니다.
        string filtered = "";
        for (auto &x:s) {
            // 만약 대문자면 소문자로 변경합니다.
            if (x >= 'A' && x <= 'Z') {
                filtered += tolower(x);
            }
            // 소문자이거나 숫자인 경우에는 그대로 저장합니다.
            else if ((x >= 'a' && x <='z') || (x >= '0' && x <='9')) {
                filtered += x;
            }
        }
        
        // 왼쪽 포인터와 오른쪽 포인트를 두고, 두 포인터의 문자가 같은지를 확인합니다.
        int l = 0, r = (int)filtered.length() - 1;
        
        // l == r 인 경우는 Palindrome이기 때문에 고려하지 않아도 됩니다.
        while(l < r) {
            
            // 만약 다르면 Palindrome이 아닙니다.
            if (filtered[l] != filtered[r]) {
                return false;
            }
            
            // 두 포인터를 한칸씩 이동합니다.
            l++;
            r--;
        }
        return true;
    }
};

 

2. 3Sum

3Sum - LeetCode

풀이 

class Solution {
public:
    void twoSum(vector<int> & nums, int first_number_index, vector<vector<int>> & ans) {
        
        // 왼쪽 포인터를 첫번째 숫자 다음번으로 지정합니다.
        // 오른쪽 포인터는 배열의 끝으로 정합니다.
        int l = first_number_index + 1, r = (int)nums.size() -1;
        
        while(l < r) {
            int sum = nums[first_number_index] + nums[l] + nums[r];
            // 세 수의 합계가 0 같으면 세 수를 정답배열에 저장합니다.
            if (sum == 0) {
                ans.push_back({nums[first_number_index], nums[l], nums[r]});
                
                // 양쪽 포인터를 이동합니다.
                l++, r--;
                
                // 중복을 제거하기 위해서 왼쪽 포인터를 중복되지 않는 수로 옮깁니다.
                // 오른쪽은 따로 진행할 필요가 없는 이유가 왼쪽 수가 커지면서 다음 차례에서 오른쪽 포인터를 움직이게 됩니다.
                while(l < r && nums[l] == nums[l-1]) {
                    l++;
                }
            } 
            // Sum이 0보다 작으면, 더 큰 값이 필요하므로 왼쪽 포인터를 한 칸 이동합니다.
            else if (sum < 0) {
                l++;
            } 
            // sum이 0보다 크면, 더 작은 값이 필요하므로 오른쪽 포인터를 한 칸 이동합니다.
            else {
                r--;
            }
        }
    }
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        
        // 세 수의 합은 2Sum 문제의 확장형입니다.
        // 먼저 1개의 수를 선택하고, 나머지 중에서 twoSum을 실행하면 됩니다.
        // 이때 Target이 되는 조합을 손쉽게 구하기 위해서 배열을 정렬합니다. 
        // 배열을 정렬하면 현재의 합계와 target의 값을 비교하여 왼쪽 또는 오른쪽 포인터를 움직일지 결정합니다.
        sort(nums.begin(), nums.end());
        
        // 배열을 순회하면서 숫자 하나를 지정합니다.
        for (int i = 0; i < (int)nums.size(); ++i) {
            // 중복을 제거합니다.
            if (i > 0 && nums[i-1] == nums[i]) {
                continue;
            }
            
            twoSum(nums, i, ans);
        }
        return ans;
    }
};

 

3. Container With Most Water

Container With Most Water - LeetCode

풀이

class Solution {
public:
    int maxArea(vector<int>& height) {
        // 왼쪽 포인터는 첫번째 원소, 오른쪽 포인터를 마지막 원소를 가리킵니다.
        int l = 0, r = (int)height.size() - 1;
        int ans = 0;
        
        // 포인터가 양쪽 끝에 있을 배열의 가로 길이는 N-1이 됩니다.
        // 이후에 가로 길이를 한 칸 줄인 경우를 따져봐야 하는데, 이 때는 양쪽 길이 중에 짧은 쪽을 움직이면 됩니다.
        // 왜냐하면 어느쪽을 움직이나 가로는 같은 값이 되지만, 큰 막대의 포인터를 움직이더라도 세로가 작은 막대보다 클 수 없습니다.
        // 따라서 짧은 쪽을 움직여서 더 긴 세로 길이가 나올 경우를 찾습니다.
        while(l < r) {
            
            // 현재 값은 양쪽 중 짧은 막대와 가로 길이의 곱으로 구합니다.
            int curr = min(height[l], height[r]) * (r - l);
            
            // max 값을 업데이트 합니다.
            ans = max(ans, curr);
            
            // 짧은 쪽의 포인터를 움직입니다.
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
};

 

 

Two Pointers 패턴은 주로 양쪽 배열 끝에서 시작하거나 한쪽에서 시작하되 서로 속도가 다르게 움직일 때 자주 사용됩니다. 중요한 점은 pointer가 Random하게 움직이는 경우에는 이를 한 방향으로 이동할 수 있도록 만든 후에 사용하는 것이 보통입니다.

---

위에서 3Sum 문제를 풀어보았는데, 이 문제의 기반은 Two Sum 문제입니다.

Two Sum과 관련한 다양한 문제풀이를 보고 싶으신 경우 아래 글도 읽어보시는 것을 추천드립니다.

Two Sum