1. 문제 설명 📌

문제 링크

일련의 수가 1차원 배열 형식으로 주어진다. 이때 수들 중 임의의 수 하나를 다른 수 두개의 합으로 나타낼 있을 때, 이 임의의 수를 좋은 수라고 한다. 이러한 좋은 수가 배열 내에 몇 개인지 구하라

2. 접근 방식 🗃️

Key Word: Two-way Two Pointer

두 포인터의 합 > target: R 포인터를 한 칸 내려 합을 하향 조정
두 포인터의 합 < target: L 포인터를 한 칸 올려 합을 상향 조정
두 포인터의 합 == target: 답을 +1 올리고 반복문 종료

(1) 시간 복잡도는?

N = 2000 으로 이중 반복문까지 허용 범위이다. 따라서

N개 중에 하나 Target 값으로 찾기 (O(N))
두 포인터 움직이며 Target 값 만들 수 있는지 찾기 (O(N))

두 움직임은 연속으로 일어나니, 최종 최악의 시간 복잡도는 ( O(N^2) ) 이다.

3. 코드 소개 🔎

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

public class Main {

    /*
    * b1253 좋다
    * (1) Target 값 찾기 O(N)
    * (2) Target 값 만들 수 있는지 확인 O(N)
    * */

    public static void main(String[] args) throws IOException {
        // 입력 받기
        int ans = 0;
        int N;
        int [] arr;
        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 i = 0; i < N; i++) {
            int target = arr[i];
            int l = 0; int r = N-1;
            while (l < r){
                if(l == i){
                    l++;
                    continue;
                }else if(r == i){
                    r--;
                    continue;
                }
                int now = arr[l] + arr[r];
                if(now < target) l++;
                else if(now > target) r--;
                else {
                    ans++;
                    break;
                }
            }
        }
        System.out.println(ans);
    }
}

4. 배운 것들 🎯

(1) 단방향 투 포인터를 못 쓰는 이유?

결론: 단방향 투 포인터는 줄어듦을 표현하지 못한다.

해당 문제에서는 (1) 두 수의 합 < target, (2) 두 수의 합 > target 인 경우 포인터를 적절히 조절해 target 값에 다가가야 한다. 양방향 포인터의 경우 (1)번의 경우 왼쪽 포인터를 한 칸 올려서 값을 상향 조정하고, (2)의 경우 오른쪽 포인터를 한 칸 내려서 하향 조정한다면 두수의 합을 증가시키거나 감소해가며 모든 경우의 수를 확인할 수 있다.

반면 단방향 투포인터의 경우 두 포인터의 움직임 모두 증가만을 표현한다. 다음의 예를 보자.

두 수의 합 > target이면 L을 ++, 두 수의 합 < target이면 R을 움직인다고 해보자. 해당 예시에서 R을 index = 10까지 움직여도 여전히 target값 보다 작다. 그래서 답을 못 찾는다. 1+2 = 3 이란 답이 입력된 값들 사이에 있음에도 말이다.