1630-kir3i.md

1630. Arithmetic Subarrays

Solution

• 시간복잡도: O(QN), Q는 쿼리의 수

• 알고리즘

  구현, 자료구조

• 풀이설명

  l과 r에 주어진 쿼리에 따라 답을 도출하면 되는 문제입니다. 핵심은 주어진 배열이 arithmetic한지 판단하는 부분인데, 이 부분을 어떻게 구현하느냐에 따라 시간복잡도가 달라집니다. 정렬을 이용할 수도 있고, Set을 이용할 수도 있습니다.

  아래 소스코드 풀이는 Set을 이용했습니다. 쿼리마다 배열의 모든 원소를 Set에 집어넣고, 공차 jump를 계산한 뒤 있어야할 값이 있는지 체크하는 방법입니다. jump는 배열의 최대, 최소값과 배열의 길이를 토대로 구할 수 있습니다.

  이 때 예외케이스 두 가지를 처리해야 합니다.

  1. 주어진 배열 전체가 하나의 값으로 이루어진 경우 arithmetic
  2. 배열의 최댓값, 최솟값의 차가 배열 길이보다 작은 경우 not arithmetic

  이 방법 말고도 쿼리마다 주어진 배열을 정렬해서 풀 수도 있으며, 이 경우 시간복잡도는 O(QNlogN)이 됩니다.

• 소스코드

  • C++

    class Solution {
    public:
        unordered_set<int> s;
        int smax, smin;
        vector<bool> ans;
        bool ok;
        vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
            int qsz = l.size();
            for (int q=0; q<qsz; q++) {
                s.clear();
                smax = -2e8;
                smin = 2e8;
                ok = true;
                for(int i=l[q]; i<=r[q]; i++) {
                    s.insert(nums[i]);
                    smax = max(smax, nums[i]);
                    smin = min(smin, nums[i]);
                }
                
                int jump = (smax - smin) / (r[q] - l[q]);
                if (smin == smax) {
                    ans.push_back(true);
                    continue;
                } else if(!jump) {
                    ans.push_back(false);
                    continue;
                }
                for(int i=smin; i<=smax; i+=jump) {
                    if(!s.count(i)) {
                        ans.push_back(false);
                        ok = false;
                        break;
                    }
                }
                
                if (ok)
                    ans.push_back(true);
            }
            return ans;
        }
    };

  • Python

    class Solution:
        def checkArithmeticSubarrays(self, nums, l, r):
            return [self.isArithmetic(nums[lo:hi+1]) for lo, hi in zip(l, r)]
    
        def isArithmetic(self, nums):
            maxn = max(nums)
            minn = min(nums)
            if maxn == minn:
                return True
    
            jump = (maxn - minn) // (len(nums) - 1)
            if jump == 0:
                return False
            setNums = set(nums)
            for x in range(minn, maxn + 1, jump):
                if x not in setNums:
                    return False
            return True