[알고리즘/투포인터] 투포인터 알고리즘

투 포인터 알고리즘 또는 슬라이딩 윈도우 기법 또는 지렁이 알고리즘 등 이름이 참 많은 알고리즘입니다.

개인적으로 이 알고리즘과 인연이 깊습니다. 알고리즘을 공부하며 처음 소름돋았던 알고리즘이기도 하며

대충 공부했었는데, 운이 좋게도 얼마 지나지 않아 응시했던 Kakao 공채 1차 코테에서 이걸 활용해 풀었습니다.

이 문제 덕분에 제 첫 코테를 통과라는 기쁨을 누렸고, 그 이후 여러 코테에서 비슷한 유형으로 마주쳤던 기억이 납니다.

솔직히 매번 쓸때마다 헷갈렸는데, 이번 기회에 제대로 학습해 올립니다.

 

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

이 문제를 바탕으로 적으려 합니다.

 

먼저 투포인터 알고리즘은 시간 복잡도가 O(N)인 효율적인 알고리즘입니다. 

start = 0, end = 0으로 시작하며, end와 start를 늘려가면서 (start <= end)인 구간을  탐색합니다.

구간은 start에서 부터 end-1까지 인데 1 2 3 4 2 5 3 1 1 2라는 배열이 있을때, start = 1, end = 4라면

실제 구간은 파란색 글씨인 2, 3, 4가 됩니다. 이렇게 검사하는 구간중에 주어진 조건(이 문제에서는 합이 M인 경우)을 만족하는지 여부를 확인하면 됩니다.

이 문제는 합이 M이 되는 구간의 개수를 묻는 것이므로 구간 합을 sum으로 계산하고 sum == M이 성립할때, result++를 해주면 됩니다.

 

종료조건은 저 같은 경우, start == N && end == N인 start와 end가 모두 N일때까지의 모든 경우를 탐색합니다.

- start의 증가 조건 : 문제의 조건이 성립(sum >= M)하는 경우를 포함하거나 end를 더이상 증가시킬 수 없을때

      -> start를 증가시킬 것이므로, 현재 start가 가르키는 곳을 sum에서 빼고 start를 증가해줍니다.

- end의 증가 조건 : 문제의 조건이 성립하지 않을 (sum < M) 경우

      -> end를 증가시킬 것이므로, 현재 end가 있는 범위를 sum에 더해주고, end를 증가해줍니다.

 

# 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class NumbersSum {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        int result = 0;
        int start = 0;
        int sum = 0;
        int end = 0;
        while (true) {
            //start 증가 조건
            if (start < arr.length && (sum >= M || end == arr.length)) {
                if (sum == M) {
                    result++;
                }
                sum -= arr[start++];
            } 
            //end 증가 조건
            else if (end < arr.length){
                sum += arr[end++];
            }
            //종료 조건
            if (start == arr.length && end == arr.length)
                break;
        }
 
        System.out.println(result);
    }
}
 

 

# 예외상황은 발생하지 않을까?

두가지 상황이 있을 수 있습니다. 우리가 구해야 하는 정답인 구간이 [S, E]라고 가정하면,

1. end = E가 되기 전에, start가 S보다 커지는 경우 : 이 경우는 성립할 수가 없습니다. 왜냐하면 만약 start = S인데 end < E일때 start가 증가해야하는데, 이 구간은 [S, E]구간보다 합이 작기 때문에 조건이 성립되지 않아 end를 무조건 증가시켜야하기 때문입니다.

2. start = S가 되기 전에, end가 E보다 커지는 경우 : 이것도 마찬가집니다. start < S일때, end = E라면 [S, E]의 구간의 조건을 포함하는 경우 이므로 start를 증가시켜야하기 때문에 성립되지 않습니다.

 

 

# 유사하면서 풀어볼만한 문제 : 2020 카카오 인턴쉽 - 보석쇼핑

https://mhwan.tistory.com/58

[알고리즘 / 투 포인터] 2020 카카오 인턴십 - 보석 쇼핑

 

 

참고 : m.blog.naver.com/kks227/220795165570