투 포인터 알고리즘(Two Pointers Algorithm)

두 포인터를 사용하여 문자열이나 정렬된 배열(또는 리스트)에서 원하는 값을 찾거나 구간합을 구할 때 유용한 알고리즘

• 슬라이딩 윈도우와 유사하나, 고정된 구간이 아닌 가변적인 구간을 탐색한다는 점에서 차이

이미지 출처 : https://emre.me/coding-patterns/two-pointers/

문제

두 숫자의 합

숫자로 된 배열이 주어지고, 두 숫자의 합(Ai + Aj)이 특정한 숫자(x)가 되는 숫자 쌍의 갯수를 구하라

솔루션

1. 배열을 정렬

   array.sort() # 오름차순 정렬

2. 포인터(인덱스) 2개를 각각 start, end로 놓고,
   start는 배열의 맨 앞(0번 인덱스), end는 배열의 맨끝(n-1번 인덱스)로 초기화

   start, end = 0, n-1

3. while문을 돌면서, 두 포인터(인덱스)에 해당하는 배열의 값을 더함
   - if 더한 값이 target 숫자보다 큰 경우, start+1
   - else if 더한 값이 target 숫자보다 작은 경우, end-1
   - else 즉, 더한 값이 target 숫자인 경우, count+1, start+=1, end-=1

   while start<end:
     	Sum = array[start] + array[end]
     	if Sum > target:
   			start += 1
         elif Sum < target:
         	end -= 1
         else:
         	count += 1
             start += 1
             end -= 1

4. start가 end보다 작은 동안만 while문을 돌림
5. 결과적으로 반복문을 마치고 나온 count 값이 정답임

관련 문제

[BOJ 3273번] 두수의 합