1995. Count Special Quadruplets

https://leetcode.com/problems/count-special-quadruplets/

난이도 : easy

 

 

문제 

입력으로 들오는 배열에서 4개의 원소를 선택하고 선택한 원소들이 a < b < c < d 와 같고 nums[a] + nums[b] + nums[c] == nums[d] 의 조건을 맞는 조합의 갯수를 출력하라.

 

INPUT 이 1,1,1,3,5 라면 문제의 제약사항에 맞게 숫자를 선택하면

1 1 1 3 = 1을 3개 더한 값은 3 이랑 같으니 패스

1 1 3 5 = 1 1 3 더한 값은 5 랑 같으니 패스 

입력으로 들어오는 배열의 MAX 크기는 50 임으로 브루트포스로 풀린다. 

 

 

코드

4중 반복문을 사용한 코드(브루트포스)

class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        int ans=0,size=nums.size();
        for(int i=0;i<size-3;i++)
        for(int j=i+1;j<size-2;j++)
            for(int k=j+1;k<size-1;k++)
                for(int l=k+1;l<size;l++)
                {
                    if(nums[i]+nums[j]+nums[k]==nums[l])
                        ans++;
                }
        return ans;
        
    }
};

 

재귀를 사용한 코드

일단 코드는 이렇게 짰는데 연산량을 줄일 수 있는 방법이 있지 않을까? 라는 생각이 든다. 가지치기 등을 사용해서 중복연산이 없게 할 수 있을까? 내공이 부족해서 잘 모르겠지만 의심은 하자.

class Solution {
public:
    int sol = 0;
    bool chosen[51];
    void calc(vector<int>& nums, vector<int>& arr, int begin) {
        
        if(arr.size() == 4) {
            int sum = 0;
            for(int i = 0; i < 3; i ++) {
                sum += arr[i];
            }
            if(sum == arr[3]) {
                sol++;
            }
        }
        else
        {
            for(int i = begin; i < nums.size(); i++) {
                if (chosen[i] == true) continue;
                chosen[i] = true;
                arr.push_back(nums[i]);
                calc(nums, arr, i + 1);
                arr.pop_back();
                chosen[i] = false;
            }
        }
    }
    
    int countQuadruplets(vector<int>& nums) {
        vector<int> arr;
        calc(nums, arr, 0);
        return sol;
    }
};

 

오전에 문제를 풀고서는 가만히 생각 해보니 for 문 부분을 아래처럼 변경하는게 더 깔끔해 보인다.

class Solution {
public:
    int sol = 0;
    bool chosen[51];
    void calc(vector<int>& nums, vector<int>& arr, int begin) {
        
        if(arr.size() == 4) 
        {
            if ((arr[0] + arr[1] + arr[2]) == arr[3]) {
                sol++;
            }
        }
        else
        {
            for(int i = begin; i < nums.size(); i++) {
                if (chosen[i] == true) continue;
                chosen[i] = true;
                arr.push_back(nums[i]);
                calc(nums, arr, i + 1);
                arr.pop_back();
                chosen[i] = false;
            }
        }
    }
    
    int countQuadruplets(vector<int>& nums) {
        vector<int> arr;
        calc(nums, arr, 0);
        return sol;
    }
};

 

위코드처럼 반복문을 제거후 Runtime 시간을 확인 해보니 425 ms 에서 260 ms 로 시간이 단축 됬다. 사소한 수정사항이라고 생각했는데 약 162 ms 정도 속도가 개선이 된것을 보고 놀랐다. ㅎㅎ