투 포인터(Two Pointers)

[투 포인터]

투 포인터 알고리즘은 리스트의 데이터에 순차적으로 접근하기 위한 알고리즘이다.

그 이름에서 알 수 있듯이 순차적 접근에 필요한 인덱스 두 개가 필요한데, 두 인덱스를 담아둘 수 있는 각각의 변수를 두고 그 값을 변경해가며 리스트에 접근한다.

 

 

---

 

[투 포인터를 활용한 예 - 특정 합의 연속된 부분 수열 개수 구하기]

만약 [3, 2, 1, 5, 4, 1, 2]와 같은 리스트가 있다고 할 때, [3, 2]나 [1, 5, 4]와 같이 원본 리스트의 원소 순서를 그대로 유지한 부분 리스트를 연속된 부분 리스트라고 한다. 이때 연속된 부분 리스트 원소의 총합이 5인 부분 리스트의 수를 구해보도록 하자.

1. 투 포인터 left, right 모두 첫번째 인덱스를 가리키도록 초기화한다.
2. left ~ right에 해당하는 원소의 합을 계산하여 다음과 같이 처리한다.
   • 원소의 합이 5와 같으면 카운팅 한다.
   • 원소의 합이 5보다 작으면 right를 1 증가시킨다.
   • 원소의 합이 5보다 크면 left를 1 감소시킨다.
3. left와 right가 모두 리스트 마지막 인덱스를 가리킬 때까지 2번을 반복한다.

위 알고리즘은 right가 증가할수록 합이 증가하고, left가 증가할 수록 합이 감소한다는 특징을 사용하고 있기 때문에 만약 음수의 원소가 있으면 사용할 수 없다는 것에 주의한다.

 

def count_continuous_sublist_sum(data, n):
    cnt = 0
    acc_sum = 0
    right = 0

    # left, right 0부터 시작
    for left in range(len(data)):
        # 부분 리스트를 이루는 원소들의 누적 합계가 n보다 작고
        # right index가 마지막 인덱스 미만일 때
        while acc_sum < n and right < len(data):
            # 누적합에 현재 더하고자 하는 인덱스인 right에 해당하는
            # 값을 더해준다.
            acc_sum += data[right]
            
            # 아직 목표로 하는 값보다 작으므로 right를 하나 증가시켜
            # 누적 합을 증가시킨다.
            right += 1
        
        # 만약 현재 left ~ right에 해당하는 부분 리스트의 값이 n과 같으면
        # 카운트를 증가 시킨다.
        if acc_sum == n:
            cnt += 1
        
        # 현 left로 시작하는 모든 부분 리스트 가운데 조건에 해당하는
        # 리스트를 모두 확인하였으므로 (n보다 큰 부분 리스트를 찾았던지
        # 못찾았던지 간에 상관 없이)
        # left의 값을 누적 합에서 빼주고, left를 1 증가 시킨다.
        acc_sum -= data[left]

    return cnt