투 포인터 유형 문제풀이 < 특정한 합을 가지는 부분 연속 수열 찾기 >

 

 

 

 

 

 

 

 

 

 

답안 예시

n = 5 # 데이터의 개수 N
m = 5 # 찾고자 하는 부분합 M
data = [1, 2, 3, 2, 5] # 전체 수열

count = 0
interval_sum = 0
end = 0

# start를 차례대로 증가시키며 반복
for start in range(n):
    # end를 가능한 만큼 이동시키기
    while interval_sum < m and end < n:
        interval_sum += data[end]
        end += 1
    
    # 부분합이 m일 때 카운트 증가
    if interval_sum == m:
        count += 1
    
    interval_sum -= data[start]

print(count)

 

작성한 답안

m = 5 # 찾고자 하는 부분합M
listNum = [1, 2, 3, 2, 5] # 전체 수열

cnt = 0
start, end = 0, 0
sumNum = int(listNum[0]) # 현재 부분합

# start 위치
def calStart(num):
    return num+1

# end 위치
def calEnd(num):
    return num+1

# 현재 부분합 계산
def cal():
    global start, end, sumNum, cnt
    
    # 현재 부분합 < 찾고자 하는 부분합 : end 증가
    if sumNum < m:
        end = calEnd(end)
        
    # 현재 부분합 >= 찾고자 하는 부분합 : start 증가
    elif sumNum >= m:
        start = calStart(start)
        
    # 현재 부분합 계산
    sumNum = 0
    for i in range(start, end+1):
        sumNum += listNum[i]
        
    # 현재 부분합 = 찾고자 하는 부분합 : cnt 증가
    if sumNum == m:
        cnt += 1
        
    # start와 end가 전체 수열의 마지막 위치가 아니면 계속
    if start != len(listNum) and end != len(listNum):
        cal()

cal()
print(cnt)

 

출처 : https://www.youtube.com/watch?v=cswJ1h-How0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9