[2270] Number of Ways to Split Array | Biweekly Contest 78 Medium

yoongyum·2022년 5월 16일
0

코딩테스트 🧩

목록 보기
38/47
post-thumbnail

🔎 문제설명

You are given a 0-indexed integer array nums of length n.

nums contains a valid split at index i if the following are true:

The sum of the first i + 1 elements is greater than or equal to the sum of the last n - i - 1 elements.
There is at least one element to the right of i. That is, 0 <= i < n - 1.
Return the number of valid splits in nums.

#한글요약
인덱스 0부터 n-1까지 리스트를 두개로 쪼갭니다.
쪼갰을 때 왼쪽의 합이 오른쪽보다 더 큰 경우가 몇개인지 확인하는 문제입니다.

Example 1

Input: nums = [10,4,-8,7]
Output: 2
Explanation: 
There are three ways of splitting nums into two non-empty parts:
- Split nums at index 0. Then, the first part is [10], and its sum is 10. 
The second part is [4,-8,7], and its sum is 3. Since 10 >= 3, i = 0 is a valid split.

- Split nums at index 1. Then, the first part is [10,4], and its sum is 14. 
The second part is [-8,7], and its sum is -1. Since 14 >= -1, i = 1 is a valid split.

- Split nums at index 2. Then, the first part is [10,4,-8], and its sum is 6.
The second part is [7], and its sum is 7. Since 6 < 7, i = 2 is not a valid split.
Thus, the number of valid splits in nums is 2.

Example 2

Input: nums = [2,3,1,0]
Output: 2
Explanation: 
There are two valid splits in nums:
- Split nums at index 1. Then, the first part is [2,3], and its sum is 5. 
The second part is [1,0], and its sum is 1. Since 5 >= 1, i = 1 is a valid split.

- Split nums at index 2. Then, the first part is [2,3,1], and its sum is 6. 
The second part is [0], and its sum is 0. Since 6 >= 0, i = 2 is a valid split.

제한 사항

  • 2<=2 <= nums.length <=105<= 10^5
  • 105<=-10^5 <= nums[i] <=105<= 10^5



🧊 파이썬 코드

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        cnt = 0
        Max = sum(nums) #총 합
        left = 0 #왼쪽 리스트합
        right = Max #오른쪽 리스트합
        for i in range(len(nums)-1):
            left += nums[i]
            right = Max - left
            if left >= right:
                cnt +=1 
                
        return cnt

제 코드를 채점했는데 속도가 상위 0%로 찍히네요..😲
이런 역사적인 은 남겨놔야지 ^^ (하남자특: 쉬운문제 맞추고 좋아함)



사실 이번 contest를 풀때 🤮만취상태로 봤는 데 다행히 두 문제는 풀었습니다. 그 이후로는 기절했습니다.
(biweekly contest는 토요일 23:30에 시작합니다. 도대체 왜)

다음 포스트에서는 못푼 두 문제를 분석하는 시간을 가져보겠습니다.

0개의 댓글