투 포인터

투 포인터 알고리즘은 배열이나 리스트를 탐색할 때 두 개의 포인터를 활용하는 방법으로, 보통 연속된 부분 배열을 찾거나, 특정 조건을 만족하는 값을 효율적으로 탐색할 때 사용된다.

💡 완전 탐색(Brute Force, O(N²))보다 훨씬 빠른 O(N) 시간 복잡도를 가질 수 있습니다.

핵심 원리

• 배열(리스트)에서 두 개의 포인터 (left, right)를 사용해 원하는 구간을 찾는다.
• 두 포인터를 한 방향으로 이동시키며 조건을 만족하는 구간을 탐색한다.
• 특정 조건을 만족하면 포인터의 이동을 조절하여 최적해를 탐색한다.

투 포인터를 적용하는 문제 유형

• 연속된 부분 배열(구간) 문제: 특정 조건을 만족하는 가장 긴/짧은 연속 부분 배열을 찾는 문제
• 두 개의 포인터를 사용한 정렬된 배열 탐색: 정렬된 배열에서 특정 값을 찾거나 두 개의 합을 구하는 문제
• 두 배열을 비교하는 문제: 두 개의 정렬된 배열을 비교하여 공통 원소를 찾거나, 두 배열의 차이를 구하는 문제

백준 30804번(과일 탕후루)

❇️ 핵심 포인트

• 과일이 꽂힌 배열에서 연속된 부분 배열 중, 최대 두 종류 이하의 과일을 포함하는 가장 긴 부분을 찾아야 함
• start(left)와 end(right) 두 개의 포인터를 사용하여 연속된 구간을 유지해야 함
• end 포인터를 확장하면서 과일을 추가하고, 과일 종류가 3개 이상이 되면 start를 이동시켜 조건을 만족하는 부분 배열을 유지함
• 최대 길이를 지속적으로 갱신하여 정답을 도출함

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

class Main {

    /**
     * 과일의 개수 n
     * 앞 또는 뒤쪽에서 과일을 빼서 두 종류 이하의 과일만 남겨야 함
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] fruitArr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            fruitArr[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(getMaxFruit(fruitArr, n));

    }


    public static int getMaxFruit(int[] fruitArr, int n) {
        // 투 포인터 (start: 왼쪽 포인터, end: 오른쪽 포인터)
        int start = 0;
        int maxLength = 0;

        // 현재 윈도우 내 과일 종류와 개수를 저장하는 HashMap
        HashMap<Integer, Integer> fruitMap = new HashMap<>();

        // 오른쪽 포인터(end)를 이동하며 탐색
        for (int end = 0; end < n; end++) {
            // 현재 과일을 윈도우에 추가
            fruitMap.put(fruitArr[end], fruitMap.getOrDefault(fruitArr[end], 0) + 1);

            // 과일 종류가 3개 이상이면, 왼쪽 포인터(start)를 이동하여 조절
            while (fruitMap.size() > 2) {
                // start 위치의 과일 개수 감소
                fruitMap.put(fruitArr[start], fruitMap.get(fruitArr[start]) - 1);

                // 만약 해당 과일 개수가 0이 되면 map에서 제거
                if (fruitMap.get(fruitArr[start]) == 0) {
                    fruitMap.remove(fruitArr[start]);
                }

                // left 포인터 이동 (불필요한 과일 제거)
                start++;
            }

            // 현재 윈도우 크기(과일 개수) 갱신
            maxLength = Math.max(maxLength, end - start + 1);
        }

        // 가장 긴 구간 반환
        return maxLength;
    }
}