[2024] day 32. 2966. Divide Array Into Arrays With Max Difference

gunny·2024년 2월 1일

2966. Divide Array Into Arrays With Max Difference 2966. Divide Array Into Arrays With Max Difference python leetcode 2966. Divide Array Into Arrays With Max Difference leetcode 2966. Divide Array Into Arrays With Max Difference python

코딩테스트

목록 보기

345/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 2월 1일 (목)
Leetcode daily problem

2966. Divide Array Into Arrays With Max Difference

https://leetcode.com/problems/divide-array-into-arrays-with-max-difference/description/?envType=daily-question&envId=2024-02-01

Problem

n개의 정수 원소로 구성된 nums와 양의 정수 k가 주어질 때,
아래의 조건을 충족하는 사이즈(크기/길이)가 3인 하나의 이상의 배열로 nums를 나눈다.

nums에서 나온 요소는 한 번만 특정 배열에 있을 수 있고,
한 배열에 있는 두 요소의 차이는 주어진 양의 정수 k보다 작거나 같아야 한다.
nums 배열을 위의 조건이 충족된 길이 3의 1d 배열로 구성해 전체 요소를 담고 있는 2d 배열로 반환한다.
조건을 만족하지 못하면 빈 리스트 '[]'를 배열하고, 답이 여러개인 경우 그 중 하나를 반환한다.

Solution

data structure

먼저 한 배열에 있는 두 요소 차이가 양의 정수 k보다 작거나 같아야 하기 때문에 가장 인접한 요소들끼리 배열되어 있어야 차례대로 검사하면서 조건을 만족시킬 수 있다. 정렬을 하지 않아도 되지만 정렬된 배열에서 연속한 요소가 쉽게 처리 될 수 있기 때문에 정렬을 수행한다.
정렬한 뒤에 길이 3씩 임시 배열을 만들고 해당 배열의 가장 작은 수, 가장 큰 수 인 양 끝단의 배열의 차이를 구해서 양의 정수 k 보다 크다면 조건에 충족되지 않으므로 빈 리스트를 반환하고 끝내고,
조건이 맞다면 임시 배열을 정답을 반환할 배열에 추가한다.

Code


class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        nums.sort()
        ans = []
        for i in range(0, len(nums),3):
            tmp = nums[i:i+3]
            if tmp[2] - tmp[0] > k:
                return []
            ans.append(tmp)

        return ans