1. 문제 설명 📌

문제 링크

N개의 수가 주어지는데, 이 중 하나를 택해보자. (택한 수를 E라 부르겠다.)
이 E를 나머지 N-1개 중 2개를 합해서 만들 수 있으면 좋은 수라고 부르겠다.
이떄 좋은 수의 개수는 몇 개 인가?

2. 구현 방법 🗃️

KEY WORD: 마주보는 투 포인터

1️⃣ N개의 수를 arr이란 배열에 입력 받아서 오름 차순 정렬한다.
2️⃣ 포인터를 3개 두어보자. 각각의 의미는 다음과 같다.
- E = 좋은 수가 될지 안될지 확인하는 target을 가리키는 포인터 (0부터 점점 오른쪽으로 간다.)
- L = N개의 정렬된 수 중 제일 좌측을 가리키는 포인터 (점점 오른쪽으로 간다.)
- R = N개의 정렬된 수 중 제일 우측을 가리키는 포인터 (점점 왼쪽으로 간다.)
3️⃣L과 R이 서로 만날 때 까지 다음을 반복한다.
- arr[E] = arr[L] + arr[R]: 좋은 수인 것이 확인되었다. 2️⃣ 다시 시작
- arr[E] > arr[L] + arr[R]: L 포인터를 ++ 해서 합이 높아지게 바꾼다.
- arr[E] < arr[L] + arr[L]: R 포인터를 -- 해서 합을 낮아지게 바꾼다.
4️⃣E가 배열의 index를 넘어설 때까지 2️⃣,3️⃣을 반복한다.

(1) 마주보는 투 포인터를 쓰는 이유? ✨

누락되는 경우의 수를 피하기 위해서 이다. 해당 문제는 N개의 수에 음수가 포함되므로 단방향 투포인터를 쓸 경우, 다음과 같은 예외가 나올 수 있다.

[-5,-4,-3,-2,-1,0,1,2,3,4,5] 라는 배열에서 현재 E가 가리키는 숫자가 3이라고 해보자. L과 R 포인터가 단방향으로 0에서부터 오른쪽으로 이동한다고 하고, 두 포인터가 가리키는 값의 합이 target보다 크면 L이 움직이고, 반대의 경우 R이 움직인다고 했을 떄, R이 배열을 벗어날 때까지 답을 찾지 못한다.

(1) 시간복잡도 분석 🕓

E 선택(2000개 ) x L과 R 만날 때까지 선택(둘이 합쳐서 최대 2000개) = 4,000,000 번의 연산이 필요하다.

따라서 SAFE!

3. 코드 소개 🔎

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, ans;
    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());
        }
        Arrays.sort(arr);
        for (int E = 0; E < N; E++) {
            int target = arr[E];
            int L = 0; int R = arr.length-1;
            while (L < R) {
                if(L == E) { L++; continue;}
                if(R == E) { R--; continue;}

                int now = arr[L] + arr[R];
                if(now == target) { ans++; break;}
                else if (now < target) L++;
                else R--;
            }
        }
        System.out.println(ans);
    }
}