[LeetCode] 2811. Check if it is Possible to Split Array

https://leetcode.com/problems/check-if-it-is-possible-to-split-array/description/

 

 

지난 주 위클리 B번 문제.(해결하지 못했다.)

아주 코포스러운 문제(?)라고 한다. 문제에서 요구하는 근본적인 문제를 해결한다면 간단한 구현으로 풀이가 가능했다.

 

1. 두 개 합쳐서 m이상인 길이 2의 배열이 하나도 없을 때 왜 불가능한가?

ex) arr =[2,1,1,1] m = 4 

문제에서 요구하는대로 진행하다보면 결국 길이 1의 subarray가 각각 1개씩, 총 2개가 남아야한다. 그러기 위해선 이전 단계에서 [길이가 2인 m보다 크거나 같은 합을 가진 subarray] , [길이가 1인 subarray]에서 split이 이루어져야 한다. 하지만 예로 든 배열에선 길이가 2인 subarray의 최대 합은 3이다. 그말인즉슨, 이전 단계에서 많은 과정을 거친다하더라도 마지막 단계를 거치지 못한다는 결론이 도출된다. 

 

arr1=[2,1] < m(=4) => 조건을 만족하지 못함

arr2=[1]  

 

그렇기 때문에 아래와 같은 간단한 구현으로 이 문제를 해결할 수 있다. (도움을 주신 피자사와님 감사합니다.)

class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        if len(nums) <= 2 : return True

        for i in range(len(nums)-1) : 
            if nums[i] + nums[i+1] >= m :
                return True

        return False