[Python] 투포인터 알고리즘 & 백준 2203 수들의 합2

투포인터

• 리스트에 순차적으로 접근해야할떄, 두개의 점의 위치를 기록하면서 처리하는 알고리즘
• 리스트에 담긴 데이터에 순차적으로 접근해야할때 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 

 

투포인터 알고리즘

1. 시작점(start)과 끝점(end)이 첫번째 원소의 인덱스(0)을 가리키도록 한다.
2. 현재 부분합이 M과 같다면 카운트한다.
3. 현재 부분합이 M보다 작다면, end를 1 증가시킨다.
4. 현재 부분합이 M보다 크거나 같다면, start를 1 증가시킨다.
5. 모든 경우를 확인할때까지 2번부터 4번까지의 과정을 반복한다.

 

백준 2203 수들의 합2

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

# 첫번째 방법 : 완전 탐색

def solution(num_list):
    cnt = 0
    for i in range(len(num_list)):
        num_sum = 0
        for j in range(i, len(num_list)):
            num_sum += num_list[j]
            if num_sum == m:
                cnt += 1
                break
            elif num_sum > m:
                break
    return cnt

print(solution(num_list))

# 두번째 방법: 투포인터 알고리즘 

def solution2(num_list):
    cnt = 0
    start, end = 0, 0
    num_sum = num_list[0]
    while True:
        if num_sum < m: # 작으면 end +1
            end += 1
            if end >= n: # 인덱스 범위 주의
                break
            num_sum += num_list[end]
        elif num_sum == m: # 같으면 cnt +1
            cnt += 1
            num_sum -= num_list[start]
            start += 1
        else: # 크면 start +1
            num_sum -= num_list[start]
            start += 1

    return cnt

print(solution2(num_list))

 

 

참고 

https://www.youtube.com/watch?v=ttLRltNDiCo