[동계 모각코 2주차 ] 투포인터 알고리즘 풀이

투포인터 알고리즘

left, right를 두어 양쪽에서 조건에 따라 1씩 줄여가면서 정답을 찾는 것.

이와 비슷한 알고리즘으로 이분 탐색이 있는데, 이는 left, right을 두고 중간 값을 이용하여 값의 범위를 반 씩 줄여가며 원하는 값을 찾아나가는 알고리즘이다.

이 두 개의 차이점으로는 가장 크게 시간 복잡도가 있는데, 이분 탐색은 O(logN), 투포인터는 O(N)으로 차이가 있다.

 

\

주어진 수들 중에 어떤 두 수를 더한 값이 주어진 수들 중에 포함이 되었는지를 찾는 문제인데, 일단 입력을 보고 개수가 일차원 배열 밖에 안되는 것을 알 수 있었다. 하지만, 시간 제한을 봤을 때 정렬이 충분히 가능한 것이 보였고 O(N) * N - 각 값에 대해 투포인터 적용으로 이렇게 O(N^2)이 나오기 때문에 충분히 해결 가능하다 생각하여 풀이를 진행하였다.

 

1. 각 수를 입력 받고 이를 정렬하기.

2. left, right을 통해 정렬된 배열의 left, right값을 더해가며 값이 있는지 찾기.

3. 찾았다면, 더하고 while 멈추기, 찾지 못했다면 left, right값 조정해주기

4. 다음 값 찾기.

 

Code

import java.io.*;
import java.util.*;
public class b_1253 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr); // 투포인터 사용을 위해 정렬
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = n - 1;
            while(true) {
                if (i == left) left++;
            
                else if  (right == i) right--;
                
                if (left >= right) break;
                // 투포인터
                if (arr[left] + arr[right] > arr[i]) right--;
                else if (arr[left] + arr[right] < arr[i]) left++;
                else {
                    cnt++;
                    break;
                }
            }
        }
        bw.write(cnt + "\n");
        bw.flush();
        bw.close();
    }
}