[ BOJ ][JAVA][1253] 좋다

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

1253번: 좋다

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	4088	961	655	22.416%

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

예제 입력 1 복사

10
1 2 3 4 5 6 7 8 9 10

예제 출력 1 복사

8

코드

/*
    좋다
    투포인터
*/
import java.io.*;
import java.util.*;

public class p1253 {
    static int n;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        process();
    }

    static void process() {
        int ans = 0;
        Arrays.sort(arr);

        for (int i = 0; i < n; i++) {
            if (possible(i)) ans++;
        }

        System.out.println(ans);
    }

    static boolean possible(int idx) {
        int lo = 0;
        int hi = n - 1;
        int target = arr[idx];
        while (true) {
            if (lo == idx) lo++;
            else if (hi == idx) hi--;

            if (lo >= hi) break;

            int sum = arr[lo] + arr[hi];

            if (sum < target) lo++;
            else if (sum > target) hi--;
            else if (sum == target) {
                return true;
            }
        }
        return false;
    }
}