[🧠 Do it! 알고리즘] 2-3. 투 포인터

🧠 목차

1. 투포인터
2. [실전 문제] 수들의 합 (백준 2018)
3. [실전 문제] 주몽 (백준 1940)

---

1. 투포인터

• 두 개의 포인터를 이용해 한 번의 순회(또는 제한된 순회)로 효율적인 탐색을 수행하는 방법이다.
• 주로 정렬된 배열, 부분합 문제, 중복 제거, 슬라이딩 윈도우, 두 배열 비교 등에 자주 쓰인다.
• 시간 복잡도: O(N)

---

2. [실전 문제] 수 들의 합 5 (백준 2018)

문제: 수 들의 합 5 https://www.acmicpc.net/problem/2018

 

문제 분석하기

• N의 최대 값: 10,000,000
• 시간제한 2초
• O(nlogn), O(n^2) 등의 알고리즘은 시간 초과 !
• O(n) 의 시간 복잡도 알고리즘을 사용해야 한다.

→ 투 포인터 사용

 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int start = 1, end = 1, sum = 1;
        int count = 1;

        while(end < N){
            if(sum == N) {
                count++;
                sum += ++end;
            } else if(sum > N) {
                sum -= start++;
            } else {
                sum += ++end;
            }
        }

        System.out.println(count);

        sc.close();
    }
}

---

3. [실전 문제] 주몽 (백준 1940)

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int target = sc.nextInt();

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);

        int count = 0;
        int start = 0;
        int end = N - 1;

        while (start < end) {
            int sum = arr[start] + arr[end];

            if (sum == target) {
                count++;
                start++;
                end--;
            } else if (sum < target) {
                start++;
            } else {
                end--;
            }
        }
        System.out.println(count);

        sc.close();
    }
}