투 포인터 알고리즘

이중 for 문을 사용하면 시간 복잡도는 $O(N^2)$이지만, 투 포인터를 사용해 $O(N)$으로 줄일 수 있다.

https://www.acmicpc.net/problem/3273 [두 수의 합 | 실버3 문제]
해당 문제에서 처음 생각한 건 이중 for문을 이용이다.

        for(int i=0; i<n; i++){
            for (int j = i + 1; j < n; j++) {
                if (sum == (arr[i] + arr[j])) {
                    cnt++;
                }
            }
        

만들어야 할 합이 나오면 cnt를 올리면서 답을 도출해낼 수는 있다.
그러나 시간 복잡도에 걸려서 시간 초과로 통과를 못 한다.
그러면 결국 다른 방법을 찾아봐야 하는데, 오랜만에 코테를 준비하는 거라 밑에 버튼 클릭해서 어떤 알고리즘을 써야하는지 봤다. 힌트로는 투 포인터
일단 투 포인터 이용하기 위해서는 받아둔 입력값에 대해 정렬을 해둘 필요가 있다.
투 포인터 알고리즘이 정렬이 된 상태에서 좌측 커서를 올릴지, 우측 커서를 내릴지를 판단해야 하기 때문이다.

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

public class a3273_두수의합 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken()); // 크기 입력
        int[] arr = new int[n];
        int cnt =  0;
        st = new StringTokenizer(br.readLine()," ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr); // 배열 오름차순으로 정렬

//        5 12 7 10 9 1 2 3 11 -> 1 2 3 5 7 9 10 11 12

        int x = Integer.parseInt(br.readLine()); // 순서쌍으로 만들 크기.
        int sum = 0;
        /*
        13 -> (1,12), (2,9), (3,10)
       
         */
        int lc = 0; // 레프트 커서
        int rc = n-1; // 라이트 커서
        while (lc < rc) {
            sum = arr[lc] + arr[rc];
            if (sum == x) {
                cnt++;
            }

            if (sum < x) {
                lc++;
            } else {
                rc--;
            }
        }
        System.out.println(cnt);

    }
}

요지는 이거다. 순서쌍의 합이 x와 일치하면 카운트를 늘리고, 합이 작다면 왼쪽 커서를 올린다. 합이 크거나 같으면 우측 커서를 내린다. 사실 합이 같을 때의 케이스를 나누는게 이해하기 좀 더 편한데, 기존에 참고했던 알고리즘이 이 둘을 묶어서 코드를 작성했던 방식이라...