Computer Science/자료구조

코드테스트 Arrays 초급 | find pivot index, minimum size Subarray sum | 코드없는 프로그래밍

토마토. 2021. 9. 5. 21:03

기본 개념 : 슬라이딩

 

영상 - 코딩 테스트,초급, find pivot index - YouTube

문제 - (2) Find Pivot Index - LeetCode

 

Find Pivot Index - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

pivot의 범위는 1에서 출발해서, len(s) - 2까지 돈다.

 

pivot 왼쪽에 있는 숫자들의 합과

pivot 오른쪽에 있는 숫자들의 합이

같으면, pivot을 return한다. 

 

내 풀이 - 푸는 데 한참 걸렸다..

class Solution:
    def pivotIndex(self, s):
      
      sum = 0
      pivot_sum = 0
      for i in range(0, len(s)):
        sum += s[i]
        
      for pivot in range(0, len(s)):
        
        if pivot > 0:
            pivot_sum += s[pivot-1]
            left = pivot_sum
            
        else:
            left = 0
        
        if left == (sum - s[pivot]) / 2:
            return pivot
            break
      else:
        return -1

 

많이 풀어본 사람은

슬라이딩 개념을 바로 떠올린다고 한다. 

 

step 1. 브루트포스법

[1,8,2,9,2,3,6]

pivot을 0(1)로 잡고, 나머지 요소를 더한다.

복잡도 O(n)

다음엔 1, 2, 3, 4, ...

이렇게 푼다면, O(n^2)의 복잡도가 발생함. 

 

step 2. 

전체 sum을 구한다. 

복잡도 O(n) 필요함

 

pivot을 0으로 잡으면, 

0 / sum - s[0]으로 분리할 수 있다. 

 

그 다음에 pivot이 1이면,

0 + s[1] / sum - s[0] - s[1]

이때 복잡도는 O(n)이다. 

최종적으로 선형적인 복잡도 나옴. 

 

올 맞게 풀었네. 

 

sample code - 이게 슬라이딩 개념이다. 

int pivotIndex(int [] nums)
{
  int sum = accumulation(nums);
  int leftSum = 0;
  int rightSum = sum;
  int pastPivotNum = 0;

  for (int idx = 0; idx<nums.length; idx++)
  {
    int num = nums[idx];
    rightSum = rightSum - num;
    leftSum = leftSum + pastPivotNum;

    if (leftSum == rightSum)
    {
      return idx;
    }
    pastPivotNum = num;
  }
  return -1;
}

 

유제 - mininum size subarray sum

(2) Minimum Size Subarray Sum - LeetCode

 

Minimum Size Subarray Sum - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

음.. 어떻게 풀어야하지.. ㅠㅠ

 

[2,3,1,2,4,3], target = 7

 

1개의 max값을 찾아

 

2개의 max값을 찾아

 

3개의 max값을 찾아

def minSubArrayLen(target, nums):
        
        sum_nums = 0
        for i in range(len(nums)):
          sum_nums += nums[i]     
        # 15
        
        if sum_nums < target:
          return 0      
    
        while True:
          if sum_nums >= target:
            break
          if nums[0] > nums[-1]:
            sum_nums -= nums[-1]
            del nums[-1]            
          elif nums[0] < nums[-1]:
            sum_nums -= nums[0]
            del nums[0]              
        return nums

target = 7
print(minSubArrayLen(target, [2,3,1,2,4,3]))  
    
"""
target = 7 [2,3,1,2,4,3]
output = 7

15


"""

음.. 이게 아닌뎅

오늘은 여기까지!

 

 

class Solution:
    def minSubArrayLen(self, target, nums):
        pass
        summ = 0
        ans_list = []
        for i in range(len(nums)):
          summ += nums[i]

        for i in range(len(nums)):
          num_sum = summ
          index = 0
          # [12345]라고 치면,
          # sum = 1+2+3+4+5

          # step 1. i == 0

          # sum_i = sum

          # if sum_i < target:
            # break
            # i의 len = 몇

          # 1 + 2 + 3 + 4 ㄱㄴ?

          # 1 + 2 + 3 ㄱㄴ? 

          # 1 + 2 ㄱㄴ?

          # 1 ㄱㄴ? 



        # [numsl, numsl+1, ..., numsr-1, numsr]
        # step 1. 전체 sum을 구한다. 
        # for i in range(num)
          # 뒤에서부터 뺀다. 
          # sum >= target인 마지막 index를 저장한다.

        # 최솟값을 return한다. 

        # 만약 없으면 0 return