기본 개념 : 슬라이딩
영상 - 코딩 테스트,초급, find pivot index - YouTube
문제 - (2) Find Pivot Index - LeetCode
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
음.. 어떻게 풀어야하지.. ㅠㅠ
[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
'Computer Science > 자료구조' 카테고리의 다른 글
singly linked list (0) | 2021.11.06 |
---|---|
LeetCode 209. Minimum Size Subarray Sum | python | Two pointer (0) | 2021.09.12 |
코딩테스트 Arrays moveZeros | 코드없는 프로그래밍 (0) | 2021.09.05 |
코딩테스트 기초 배열 Binary Search | 코드없는 프로그래밍 (0) | 2021.09.05 |
코딩테스트 Arrays 이론 | 코드없는 프로그래밍 (0) | 2021.09.05 |