1630. Arithmetic Subarrays

Arithmetic Subarrays - LeetCode

 

Input: nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]
Output: [true,false,true]

Explanation:
In the 0th query, the subarray is [4,6,5].
This can be rearranged as [6,5,4], which is an arithmetic sequence.

In the 1st query, the subarray is [4,6,5,9].
This cannot be rearranged as an arithmetic sequence.

In the 2nd query, the subarray is [5,9,3,7].
This can be rearranged as [3,5,7,9], which is an arithmetic sequence.

설명하기 어려워서 예제로 대체.

 

요약하면 nums, l, r이라는 list가 들어온다.

num [l [i] : r [i]+1] 내부의 정수 값이 등차수열이면 True, 아니라면 False를 넣은 결과 list를 반환하는 문제다.

 

1. 정렬 사용하지 않고 풀기

class Solution:
    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
        index = 0
        answer = []
        while index < len(l):
            left, right = l[index], r[index]
            target_list = nums[left:right + 1]
            set_list = set(target_list)
            max_val, min_val = max(set_list), min(set_list)
            length = len(target_list)

            gap = (max_val - min_val) // (length - 1)
            try:
                if len(set_list) == 1:
                    answer.append(True)
                elif len(set_list) != length:
                    answer.append(False)
                else:
                    left, right = min_val + gap, max_val - gap

                    while left <= right:
                        if left not in set_list:
                            answer.append(False)
                            break
                        if right not in set_list:
                            answer.append(False)
                            break
                        left, right = left + gap, right - gap

                    if left > right:
                        answer.append(True)
            finally:
                index += 1
        return answer

이 문제는 정직하게 구현하면 다음과 같이 풀 수 있다.

1. num [l [i] : r [i]+1]을 구해 temp라고 하면
2. temp.sort()를 하고
3. 내부를 순회하면서 값의 차이가 동일한지 체크한다.

그러면 매 쿼리마다 정렬 1번, 선형 탐색 1번을 하게 되는데 시간 복잡도는 O(nlogn)이 된다.

 

위 방법은 집합을 이용했다.

1. num [l [i] : r [i]+1]을 구해 temp라고 하면
2. max(temp), min(temp) 값을 구해놓고,
3. temp를 집합으로 만들고 set_list라고 한다.
4. 만일 등차 수열이라면 (max(temp) - min(temp)) / len(temp)의 값이 등차가 나오게 되고 이를 d라고 한다면,
5. min(temp)+ d, max(temp)-d가 set_list에 있는지 반복하면서 체크한다.
   
   1. 이 부분도 min(temp)에서만 시작하는 게 아니라 max(temp)에서도 같이 시작해서 선형 탐색 시간을 절반으로 줄일 수 있다.

추가적으로 위 조건 이전에 탈출할 수 있다면 결과를 바로 반환하고 탈출했다.

1. 만약 list를 집합으로 바꿀 때 집합의 길이가 1이라면 list의 모든 값이 중복이라는 뜻이고, 이는 공차가 0인 등차수열일 수밖에 없다. 이 경우는 바로 True를 반환
2. 만약 list를 집합으로 바꿀 때 집합의 길이가 1이 아니면서 기존 list의 길이와 다르다면 중복된 값이 존재하는 뜻이다. 중복된 값이 존재한다는 뜻은 절대로 등차수열을 만들 수 없기 때문에 바로 False를 반환

 

그냥 정직하게 정렬을 사용했을 때 TLE가 나는지까진 확인하지 않았다.

참고로 Python에서 set을 쓰는 것은 내부적으로 정렬을 하는 것이 아니라 hash를 사용하는 것으로 알고 있고, 만약에 key값이 정렬되는 자료구조(TreeMap, MultiSet 등)는 정렬도 사용하는 것이기 때문에 그냥 정렬하는 것과 다를 게 없다고 알고 있다.