투 포인터

이번에는 투 포인터 알고리즘에 대해서 정리해보려고한다.

Two Pointer?

• 투 포인터 알고리즘은 하나의 배열에서 두개의 원소를 가리키는 서로 다른 인덱스를 움직이며 답을 내는 알고리즘이다.
• 한 방향으로만 인덱스를 증가시켜 원하는 값을 얻어오게되는 것이다.
• 예를 들어 살펴보자. (1 3 5 7 9, 연속된 여러 원소의 합이 10을 넘는 경우가 몇 번있는가?)
  • 1회
    • start : 0, end : 1, cnt : 0
    • sum : 1 + 3 = 4
    • 합계가 10을 넘지 않으므로 end를 1증가 시킨다.
  • 2회
    • start : 0, end : 2, cnt : 0
    • sum : 1 + 3 + 5 = 9
    • 합계가 10을 넘지 않으므로 end를 1증가 시킨다.
  • 3회
    • start : 0, end : 3, cnt : 0
    • sum : 1 + 3 + 5 + 7 = 16
    • 합계가 10을 넘으므로 cnt를 1증가 시키고 start를 1증가 시킨다.
  • 4회
    • start : 1, end : 3, cnt : 1
    • sum : 3 + 5 + 7 = 15
    • 합계가 10을 넘으므로 cnt를 1증가 시키고 start를 1증가 시킨다.
  • 5회
    • start : 2, end : 3, cnt : 2
    • sum : 5 + 7 = 12
    • 합계가 10을 넘으므로 cnt를 1증가 시키고 start를 1증가 시킨다.
  • 6회
    • start : 3, end : 3, cnt : 3
    • sum : 7 = 7
    • 합계가 10을 넘지 않으므로 end를 1증가 시킨다.
  • 7회
    • start : 3, end : 4, cnt : 3
    • sum : 7 + 9 = 16
    • 합계가 10을 넘으므로 cnt를 1증가 시키고 start를 1증가 시킨다.
  • 8회
    • start : 4, end : 4, cnt : 4
    • sum : 9 = 9
    • 합계가 10을 넘지 않으므로 end를 1증가 시킨다.
  • 9회
    • start : 4, end : 5, cnt : 4
    • 반복문이 종료된다.
  • 출력 : 4
• 위의 예시에서 볼 수 있다시피, start와 end의 인덱스를 지정해두고 증가시키면서 탐색을한다.
• 그 사이에 있는 값의 합을 통해 원하는 목표값을 넘은 개수를 세게 되는 것이다.

코드(Java)

int start = 0, end = 0;
int sum = 0, cnt = 0;

while(end < num){
    if(sum > target){
        cnt ++;
        sum -= arr[start];
        start ++;
    }else{
        sum += arr[end];
        end ++;
    }
}
if(sum > target) {
    cnt++;
}

시간복잡도

• 투 포인터는 두 개의 포인터가 배열 위를 탐색한다.
• 그렇기 때문에 Two Pointer는 O(n)의 시간 복잡도를 가지고 있다.