1253번 좋다

문제

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

접근 방식

투포인터

처음에는 |Ai| ≤ 1,000,000,000 조건을 고려 못하고 right 포인터를 기준 idx - 1로 잡았다가 틀렸다.

배열의 값들이 음수 양수 포함인걸 고려해서 left = 0, right = N - 1로 잡고 투포인터를 수행하되, 서로 다른 위치에 있는 두 수의 합 = a[idx]므로 기준 idx와 다른 left, right이 겹치지 않도록 주의하면 된다.

코드

public class Main {
    static int n;
    static long[] nums;

    private static int two_pointer(int idx){
        int left = 0;
        int right = n - 1;
        while (left < right){
            // 다른 두 수의 합 보장
            if (left == idx) { left++; continue; }
            if (right == idx) { right--; continue; }

            if (nums[left] + nums[right] == nums[idx]) return 1;
            else if (nums[left] + nums[right] > nums[idx]) right--;
            else left++;
        }
        return 0;
    }

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

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

        int count = 0;
        for (int i = 0; i < n; i++){
            count += two_pointer(i);
        }

        System.out.println(count);
    }
}