투포인터(two pointer) 파이썬 구현

투 포인터(two pointer)

배열에서 두 개의 포인터를 이용해 양 끝에서 탐색해 나가며 답을 찾는 방식

 

Q. 주어진 배열에서 합이 27인 경우를 찾아라

1. 최초에 맨 끝인 1과 28을 가리킨다.
2. 찾아야 하는 값(27)이 29보다 작으므로 오른쪽 포인터를 하나 감소시킨다. (1, 25 가리킴)
3. 찾아야 하는 값(27)이 26보다 크므로 왼쪽 포인터를 하나 증가시킨다. (3, 25)
4. 찾아야 하는 값(27)이 28보다 작으므로 오른쪽 포인터를 하나 감소시킨다. (3, 22)
5. 찾아야 하는 값(27)이 25보다 크므로 왼쪽 포인터를 하나 증가시킨다. (5, 22)
6. 찾아야 하는 값(27)이 두 포인터가 가리키는 값의 합과 같으므로 5와 22를 return 한다.
   1. 또 다른 순서쌍이 존재할 수 있으니 계속 진행한다. (중복된 값이 없기 때문에 양쪽 포인터를 모두 진행시킨다) (6, 19)
   2. 찾아야 하는 값(27)이 25보다 크므로 왼쪽 포인터를 하나 증가시킨다. (9, 19)
   3. 찾아야 하는 값(27)이 28보다 작으므로 오른쪽 포인터를 하나 감소시킨다. (9, 17)
   4. 찾아야 하는 값(27)이 26보다 크므로 왼쪽 포인터를 하나 증가시킨다. (11, 17)
   5. 찾아야 하는 값(27)이 28보다 작으므로 오른쪽 포인터를 하나 감소시킨다. (11, 16)
   6. 찾아야 하는 값(27)이 두 포인터가 가리키는 값의 합과 같으므로 11과 16을 return 한다.
      1. 또 다른 순서쌍이 존재할 수 있으니 계속 진행한다. (중복된 값이 없기 때문에 양쪽 포인터를 모두 진행시킨다) (12 = 12)
      2. 찾아야 하는 값(27)은 24와 같지 않다.
      3. 더 진행하면 더 이상 l ≤ r 조건을 만족하지 않기 때문에 종료한다.

구현

arr = [3, 9, 25, 22, 1, 6, 5, 11, 19, 28, 17, 12, 16] # 주어진 배열. 중복 수 없음
S = 27 # 목표 합계

arr.sort()
l, r = 0, len(arr) - 1
while l <= r:
    if arr[l] + arr[r] > S:
        r -= 1
    elif arr[l] + arr[r] < S:
        l += 1
    elif arr[l] + arr[r] == S:
        print(l, '번째 수 (', arr[l], ') + ', r, '번째 수 (', arr[r], ')')
        r -= 1
        l += 1

결과