투 포인터(Two Pointer)

문딤·2022년 8월 15일

알고리즘

투 포인터란?

강의 내용

값을 가리키는 두 개의 변수
배열에서 두 개의 포인터를 사용해서 원하는 결과를 얻는다.

배치방법
같은 방향에서 시작, 다른 방향에서 시작...?(이분탐색이랑 다른게 뭐야)

다중 for문의 복잡도를 선형적으로 풀이 가능.

예제

같은 방향으로 진행


public static int[] twoPointers(int[] arr, int target) {
        int p1 = 0;
        int p2 = 0;
        int sum =0;
        int cnt =0;
        int [] result = {-1,-1};


        while(true){
            if(sum > target){
                //타겟 value 보다 sum 이 클때
                sum -= arr[p1++];
                // start 인덱스를 늘리고 sum은 이전 값으로 삭제
                //전에 있던 인덱스를 하나 줄이고
                // 인덱스는 하나 키운다.
            }else if(p2 == arr.length){
                //끝까지 갔다면 break;
                break;
            }else{
                // end 인덱스를 계속 추가해주면서
                // sum 보다 크면 start를 줄이고
                // 작으면 end를 키운다.
                sum += arr[p2++];
            }
            if(sum == target){
                result[0] =p1;
                result[1] =p2-1;
                cnt++;
                //인덱스
                break;
            }

        }
        System.out.println(cnt);
        return result;
        }

다른 방향으로 진행

 public static long getCount(int X) {

        long count = 0;
        int s = 0, e = arr.length - 1;

        while (s < e) {

            long sum = arr[s] + arr[e];

            if (sum == X) {
                int a = arr[s];
                int b = arr[e];
                long acnt = 0, bcnt = 0;

                while (s < arr.length && arr[s] == a) {
                    s++;
                    acnt++;
                }
                while (e >= 0 && arr[e] == b) {
                    e--;
                    bcnt++;
                }
                count += acnt * bcnt;
            }

            else if (sum > X)
                e--;

            else if (sum < X)
                s++;
        }
        return count;
    }

같은 방향 배열 1개 BOJ2003

  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());

    st = new StringTokenizer(br.readLine()," ");
    int [] arr = new int[N];
    for (int i = 0; i < N; i++) {
            arr[i] =Integer.parseInt(st.nextToken());
        }
    int cnt=0;
    int left =0;
    int right =0;
    int sum =0;

    while(left <= N && right <= N){

        if(sum >= M){
            sum -= arr[left++];
        }else if(right == arr.length){
            break;
        }else{
            sum += arr[right++];
        }
        if(sum == M){
            cnt++;
        }
    }
        System.out.println(cnt);
    }

다른 방향 배열 1개 예제 BOJ3273

 public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력
        int n = Integer.parseInt(br.readLine());

        int []arr = new int [n];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for (int i = 0; i < n; i++) {
            arr[i] =Integer.parseInt(st.nextToken());
        }
        int m = Integer.parseInt(br.readLine());
        Arrays.parallelSort(arr);
        int left = 0;
        int right =n-1;
        int sum = 0;
        int count =0;

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

        }
        System.out.println(count);

    }