[Leetcode] 923. 3Sum With Multiplicity 문제 풀이

https://leetcode.com/problems/3sum-with-multiplicity/

3Sum With Multiplicity - LeetCode

 

문제 내용

배열 중에 숫자 3개의 합이 target이 되는 경우의 수가 몇개 있는 지 찾는 문제

 

Example 1:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: 
Enumerating by the values (arr[i], arr[j], arr[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

Example 2:

Input: arr = [1,1,2,2,2,2], target = 5
Output: 12
Explanation: 
arr[i] = 1, arr[j] = arr[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

 

문제 풀이

1. two pointer 사용

정렬된 배열에서 1개를 선택하면 2개의 변수가 남는다.

2개 변수를 양쪽 끝에서 오면서 target 이 되는 지 확인했다.

여기서 2개의 case가 나왔는데

1. 양쪽 변수가 같은 경우에는 1~n까지 더하는 수학공식을 사용했다.
   양쪽 변수가 같다는 뜻은 내부 변수도 전부 같다는 의미이다.
   변수가 다 같을 경우 2개 뽑는 경우의 수는
   첫번째 선택했을 때 n-1개
   두번째 선택했을 때 n-2개
   ...
   하면 결국 1부터 n까지 더하는 공식 = n*(n+1) / 2 이 된다.
   
   
2. 양쪽 변수가 다를 경우에는 각각 중복되는 개수를 구해서 곱셈으로 경우의수를 구했다.
   양쪽 변수가 다르면 양쪽에서 한개씩 뽑는다고 생각하면 결국 왼쪽 n개 랑 오른쪽 m개가 서로 곱한게 경우의 수가 된다.

그리고 target - arr[i] - arr[s] - arr[e] 한 값이

음수면, 큰 수가 필요하니 왼쪽에 있는 작은 숫자를 한칸 이동하면 되고

양수면, 작은 수가 필요하니 오른쪽에 있는 큰 숫자를 줄이게 한칸 이동하면 된다.

2. count hash 사용

2개 변수를 2중 for문으로 돌면서 마지막 변수를 count hash로 몇개인지 구하는 방법이다.

값의 범위가 0~100까지로 작기 때문에  값을 해시키로 사용 가능하다.

 

값 v = target - arr[i] - arr[j]가 hash에 몇개 있는 지 ans에 계속 더하면 된다.

그리고 j가 한칸 갔을 때 hash에 arr[j] 을 추가한다.

j가 지나는 값이 몇개인지 count 해서 사용하기 때문이다.

i를 기준으로 새로 count hash 기록한다.

 

hash는 사용할 수 있는 값의 집합같은 개념으로 보면 된다.

즉, 어떤 값 x가 몇개가 있는 지 저장하는 count hash이다.

예를 들어, count[1] = 2 이면 x=1이 2개가 집합에 있고 그 2개를 쓸 수 있다는 뜻이 된다.

2개를 쓸 수 있다는 것은 2번 가능 하다는 뜻이고 경우의 수가 2라는 의미이다.

그래서 ans += count[1] 을 할 수 있다.

 

count[v] 의 의미는 target = arr[i] + arr[j] + v 인데 해당 값 v가 몇개 있는 지 찾는 다는 뜻이다.

count[arr[j]]++ 의 의미는 arr[j] 값을 count hash 집합에 1개 추가한다는 뜻이다.

j는 한칸씩 ++ 하기 때문에 사용한 arr[j]는 count hash 집합에 추가하고,

다음 arr[j+1] 때 count hash 집합에 요긴하게 사용할 수 있다.

 

코드

two pointer 사용

class Solution {
public:
    const int mod = 1e9+7;
    
    int threeSumMulti(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());
        
        long ans = 0;
        for (int i = 0; i < arr.size(); ++i) {
            int newTarget = target - arr[i];
            
            int s = i+1;
            int e = arr.size()-1;
            while (s < e) {
                int value = newTarget - (arr[s] + arr[e]);
                if (value == 0) {
                    if (arr[s] == arr[e]) {
                        int n = e - s;
                        ans += n*(n+1)/2;
                        break;
                    } 
                    
                    int s_count = 1;
                    while (s+1 < e && arr[s] == arr[s+1]) {
                        ++s;
                        ++s_count;
                    }
                    int e_count = 1;
                    while (s < e-1 && arr[e] == arr[e-1]) {
                        --e;
                        ++e_count;
                    }
                    ans += s_count * e_count;
                }
                
                if (value > 0) {
                    ++s;
                } else {
                    --e;
                }
            }
        }
        return ans % mod;
    }
};

 

count hash 사용

class Solution {
public:
    const int mod = 1e9+7;
    int threeSumMulti(vector<int>& arr, int target) {
        int ans = 0;
        for (int i = 2; i < arr.size(); ++i) {
            vector<int> count(101, 0);
            for (int j = 0; j < i; ++j) {
                int v = target - arr[i] - arr[j];
                if (0 <= v && v <= 100) {
                    ans = (ans + count[v]) % mod;
                }
                count[arr[j]]++;
            }
        }
        return ans;
    }
};