목차

• two pointer 이용해 3개 distinct한 원소의 합으로 target을 구할 수 있는 경우의 수 구하기
• sliding window와 counting map을 이용해서 Xth smallest integer를 구하기
• Counting map을 이용해 목표 지점의 pointer 존재 여부 확인하기

---

two pointer 이용해 3개 distinct한 원소의 합으로 target을 구할 수 있는 경우의 수 구하기

• 3Sum With Multiplicity

• 풀이

• 문제 요약
  • int array가 주어졌을 때, 3개의 distinct한 원소의 합으로 target을 구할 수 있는 경우의 수를 구하라.
• 풀이 요약
  • Brute Force
    • Time Complexity: $O(n^3)$
    • 3중 for문을 사용하여 모든 경우의 수를 비교한다.
    • input size가 3000이므로 이 방법은 시간 초과가 발생한다.
  • 개선 풀이
    • Time Complexity: $O(n^2)$
    • int array를 정렬한다
    • two pointer를 사용하여 3개의 distinct한 원소의 합으로 target을 구할 수 있는 경우의 수를 구한다.
      • left, right의 합이 target보다 작으면 left를 증가시킨다.
      • left, right의 합이 target보다 크면 right를 감소시킨다.
      • left, right의 합이 target과 같으면 left, right의 원소가 같지 않은 경우와 같은 경우를 나누어 계산한다.
        • left, right의 원소가 같지 않은 경우: right와 left의 원소의 개수를 곱한다.
        • left, right의 원소가 같은 경우: right - left + 1개의 원소 중 2개를 선택하는 경우의 수를 구한다.

#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 1e9 + 7;

long long countPairs(const vector<int>& arr, int& left, int& right, int targetSum);
long long countSameElements(const vector<int>& arr, int& index, int end);
long long countSameElementsReverse(const vector<int>& arr, int& index, int start);

int threeSumMulti(vector<int>& arr, int target) {
    int n = arr.size();
    sort(arr.begin(), arr.end());
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        int targetSum = target - arr[i];
        int left = i + 1;
        int right = n - 1;
        ans = (ans + countPairs(arr, left, right, targetSum)) % MOD;
    }

    return ans;
}

long long countPairs(const vector<int>& arr, int& left, int& right, int targetSum) {
    long long ans = 0;

    while (left < right) {
        int sum = arr[left] + arr[right];

        if (sum < targetSum) {
            left++;
        } else if (sum > targetSum) {
            right--;
        } else {
            if (arr[left] != arr[right]) {
                int countLeft = countSameElements(arr, left, right);
                int countRight = countSameElementsReverse(arr, right, left);
                ans += static_cast<long long>(countLeft) * countRight;
                ans %= MOD;
            } else {
                int count = right - left + 1;
                ans += static_cast<long long>(count) * (count - 1) / 2;
                ans %= MOD;
                break;
            }
        }
    }

    return ans;
}

long long countSameElements(const vector<int>& arr, int& index, int end) {
    int count = 1;
    while (index + 1 < end && arr[index] == arr[index + 1]) {
        count++;
        index++;
    }
    index++;
    return count;
}

long long countSameElementsReverse(const vector<int>& arr, int& index, int start) {
    int count = 1;
    while (index - 1 > start && arr[index] == arr[index - 1]) {
        count++;
        index--;
    }
    index--;
    return count;
}

sliding window와 counting map을 이용해서 Xth smallest integer를 구하기

• Sliding Subarray Beauty

• 풀이

• 문제 요약
  • beauty of subarray는 subarray의 Xth smallest integer를 말한다.
  • 이 때, Xth smallest integer가 negative일 경우, beauty는 0이다.
  • n - k + 1 개의 subarray의 beauty로 이루어진 array를 구하라.
• 풀이
  • Brute Force
    • Time Complexity: $O(n^2)$
    • 모든 subarray의 beauty를 구한다.
  • 개선 풀이
    • Time Complexity: $O(n)$
    • sliding window와 counting map을 사용하여 beauty를 구한다.
      • n - k + 1개의 subarray의 크기는 k이다.
      • k개의 subarray를 구하기 위해 sliding window를 사용한다.
      • 이 때, counting map을 사용하여 Xth smallest integer를 구한다.
      • negative한 수를 처리하기 위해 negative한 수를 0으로 처리한다.
      • Xth smallest integer를 구하기 위해 counting map의 frequency sum을 활용한다.

#include <deque>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        vector<int> transformed_nums = transformNums(nums);
        vector<int> res;

        deque<int> window;
        map<int, int> count_map;

        for (int i = 0; i < transformed_nums.size(); ++i) {
            if (i >= k) {
                removeElementFromWindow(window, count_map);
            }

            addElementToWindow(transformed_nums[i], window, count_map);

            if (i >= k - 1) {
                pushXthElement(count_map, x, res);
            }
        }

        return res;
    }

private:
    vector<int> transformNums(const vector<int>& nums) {
        vector<int> transformed_nums;
        transformed_nums.reserve(nums.size());

        for (auto num : nums) {
            if (num < 0) {
                transformed_nums.push_back(num);
            } else {
                transformed_nums.push_back(0);
            }
        }

        return transformed_nums;
    }

    void addElementToWindow(int element, deque<int>& window, map<int, int>& count_map) {
        window.push_back(element);
        count_map[element]++;
    }

    void removeElementFromWindow(deque<int>& window, map<int, int>& count_map) {
        int to_remove = window.front();
        window.pop_front();
        if (--count_map[to_remove] == 0) {
            count_map.erase(to_remove);
        }
    }

    void pushXthElement(const map<int, int>& count_map, int x, vector<int>& res) {
        int count = 0;
        for (const auto& [num, freq] : count_map) {
            count += freq;
            if (count >= x) {
                res.push_back(num);
                break;
            }
        }
    }
};

---

Counting map을 이용해 목표 지점의 pointer 존재 여부 확인하기

• Minimum Area Rectangle

• 풀이

• 문제 요약
  • 2차원 좌표의 array가 주어졌을 때, minimum area rectangle을 구하라.
• 풀이 요약
  • Brute Force
    • Time Complexity: $O(n^4)$
    • 4중 for문을 사용하여 모든 경우의 수를 비교한다
  • 개선 풀이
    • Time Complexity: $O(n^2)$
    • counting map을 사용하여 목표 지점의 pointer 존재 여부를 확인한다.
      • 2차원 좌표의 array를 counting map에 저장한다.
      • 2중 for문을 사용하여 모든 경우의 수를 비교한다.
        • (x1, y1), (x2, y2)의 좌표가 주어졌을 때, x1 != x2 && y1 != y2인 경우에 대해서만 확인한다.
        • (x1, y2), (x2, y1)의 좌표가 존재하는지 확인한다.
        • 존재한다면, minimum area rectangle을 구한다.

#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        int n = points.size();
        unordered_map<int, unordered_set<int>> m;
        for (auto& p : points) {
            m[p[0]].insert(p[1]);
        }
        int res = INT_MAX;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                auto& p1 = points[i];
                auto& p2 = points[j];
                if (isParallel(p1, p2)) continue;
                if (isPointExist(m, {p1[0], p2[1]}) && isPointExist(m, {p2[0], p1[1]})) {
                    res = min(res, rectangleArea(p1, p2));
                }
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

private:
    bool isParallel(const vector<int>& p1, const vector<int>& p2) {
        return p1[0] == p2[0] || p1[1] == p2[1];
    }

    bool isPointExist(const unordered_map<int, unordered_set<int>>& m, pair<int, int> point) {
        return m[point[0]].count(point[1]) > 0;
    }

    int rectangleArea(const vector<int>& p1, const vector<int>& p2) {
        return abs(p1[0] - p2[0]) * abs(p1[1] - p2[1]);
    }

---

---

2024-10-20

←이전 글: LIS - 완전 탐색에서 동적 계획법까지 다음 글: 10월 5주차 알고리즘 문제 → 카테고리로 돌아가기 ↩