bj 1253 좋다(투 포인터)

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

 

N개의 수가 주어졌을 때, 두 개의 수의 합으로 만들어질 수 있는 수를 센다.

 

N이 2000이기 때문에 완전 탐색을 하면, 시간 초과가 난다. 2000*1999*1998

즉, 2000*1999(두개의 수의 합을 구하는 부분)을 최적화 해주면 될 것이라 생각했다.

 

투 포인터로 O(N)을 만들어 2000 * 1999로 만들 수 있다.

투 포인터는 탐색을 위한 접근법이고,

이분 탐색은 탐색 그 자체이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] arr;
    static boolean[] checked;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer stringTokenizer;
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        arr = new int[N];
        checked = new boolean[N];

        String str = bufferedReader.readLine();
        stringTokenizer = new StringTokenizer(str);
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
        Arrays.sort(arr);

        int cnt = 0;
        for(int i = 0; i < N; i++){
            int start = 0;
            int end = arr.length-1;
            while(true) {
                if (start == i) {
                    start++;
                } else if (end == i) {
                    end--;
                }

                if (start >= end) break;

                if (arr[start] + arr[end] > arr[i]) {
                    end--;
                } else if (arr[start] + arr[end] < arr[i]) {
                    start++;
                } else {
                    cnt++;
                    break;
                }
            }
        }
        System.out.println(cnt);
    }
}