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

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

절대 정답이 되지 않는 경우를 Skip하는 알고리즘.

보통 a부터 b까지의 합이 ~되는 경우를 묻는 문제에서 이중 포문을 사용해야하는데

경과되는 시간을 줄이기 위해 사용하는 알고리즘이다.

위의 배열에서 i번쨰 인덱스부터 j번째 인덱스까지 합이 7이 되는 경우의수를 모두 구하는 문제라 가정해보자.

(배열의 길이가 짧아 이중포문을 사용하면 금방 구할 수 있지만 배열의 크기가 어느 수준 길어지면 시간초과가 발생한다.)

투 포인터스 알고리즘은

Left (시작:0), Right (시작:0)을 선언하고

Right를 한칸씩 이동시키면서 답을 찾으면 Left를 한칸 이동시키는 알고리즘이다.

Right를 이동시켜줄떄마다 변한 Right에 위치하는 값을 sum에 추가시켜주고

Left를 이동시켜줄떄마다 변한 Left에 위치하는 값을 빼줘야한다.

    while (left <= right && right < n) {
 
        if (sum < m) {
            
            ~~
 
            if (right < n) {
                right += 1;
                sum += arr[right];
            }
        }
        else if (sum >= m) {
    
            ~~
 
            if (left <= right) {
                sum -= arr[left];
                left++;
            }
        }
 
    }

ㅇ

이외 경우에 따라 알고리즘을 변형시켜 사용하면 된다.