[Algorithm] two pointer

two pointer
O(NlogN)

정렬된 데이터를 기준으로 사용할 수 있다.

left와 right 포인터 두개를 사용하여 탐색한다.

 

자료 출처: https://youtu.be/SrMk-EdWRUE

 

https://www.acmicpc.net/problem/1253

1253번: 좋다

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(br.readLine());
            // data는 음수값이 나올 수 있다고 가정
            long[] data = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();

            // 정렬
            Arrays.sort(data);

            // 투포인터 - ex) 두개의 수의 합이 기준이 되는 데이터의 수를 세는 규칙
            int count=0;
            for(int idx=0; idx<N; idx++){
                int left=0, right=N-1; // 맨 앞과 맨 뒤에 포인터 찍음
                long point = data[idx]; // 기준이 되는 데이터

                while(left < right){
                    if(left == idx) left++; // 기준이 되는 데이터의 인덱스라면 넘기기
                    if(right == idx) right--; // 기준이 되는 데이터의 인덱스라면 넘기기
                    if(left >= right) break; // left<right가 아니라면 탐색 종료

                    long sumN = data[left] + data[right];
                    if(sumN > point){ // 앞으로 당기기
                        right--;
                    }else if(sumN < point){ // 뒤로 밀기
                        left++;
                    }else{
                        count++;
                        break; // 찾았다면 탐색 종료
                    }
                }
            }

            System.out.println(count);
        } catch (Exception e) {
            System.out.println(e);
        }
    }
}