[백준 2002번] 수들의 합 2 - python / 투 포인터

문제 링크

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

풀이 

투포인터(Two Pointers) 문제 

: 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘 

: 시작점과 끝점으로 접근할 데이터의 범위 표현

: 완전 탐색 문제에서 시간 초과가 발생할 때 접근 가능 

 

start, end 두개의 포인터를 사용한다.

start는 부분 배열의 앞 쪽을 가리키는 인덱스, end는 부분 배열의 뒤 쪽을 가리키는 인덱스이다. 

두 포인터는 항상 start <= end 를 만족해야 한다. 

매 순간마다 부분 배열의 합과 구해야하는 값을 비교하여 포인터를 이동시킨다. 

1. 부분합 배열의 합 < 구해야하는 값 

end를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 증가시킨다.

2. 부분합 배열의 합 >= 구해야하는 값 

start를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 감소시킨다. 

n, m = map(int,input().split())

data = list(map(int,input().split()))

# 시작과 끝 
start, end = 0, 1 
cnt = 0 

while start <= end and end <= n :
	# 부분 배열의 합 
    sum_num = sum(data[start:end])
    
    if sum_num == m:
        cnt += 1 
        start += 1
    
    # 부분합 배열의 크기 증가 
    elif sum_num < m:
        end +=1 
    # 부분합 배열의 크기 감소 
    else :
        start += 1 
    
print(cnt)