[Java] 투 포인터 알고리즘 / 백준 1253번

💡 투 포인터

: 배열이나 리스트에서 '두 개의 포인터를 사용하여 '특정 구간을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘

 

• 보통 왼쪽 포인터와 오른쪽 포인터를 사용하며, 각각 탐색 범위의 시작과 끝을 가리킵니다.
• 왼쪽 포인트를 고정한 상태에서 오른쪽 포인터를 이동하거나, 조건에 따라 왼쪽 포인트도 이동하며 탐색합니다.
• 한 번의 반복으로 모든 요소를 처리하는 선형 시간 복잡도 O(n)을 가집니다. 즉, 수행 시간이 배열이나 리스트 크기에 비례합니다.
• 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나, 조건을 만족하는 부분 배열의 길이 등을 계산하는 문제에 활용

---

단계

1. 배열 또는 리스트의 시작 위치에 첫 번째 포인트와 두 번째 포인트를 설정합니다.
2. 두 포인터 사이의 구간을 조사하며 조건을 만족하는지 확인합니다.
3. 포인터를 이동시키며 다음 구간을 탐색합니다.

---

종류

고정 길이 슬라이딩 윈도우

• 고정된 길이의 윈도우(조건을 만족하는지 확인하는 구간)를 사용하여 배열이나 리스트를 탐색합니다.
• 윈도우의 크기를 일정하게 유지하므로 왼쪽 포인터와 오른쪽 포인터를 함께 이동시킵니다.
• 부분 배열의 합이나 평균을 계산하는 문제에 활용합니다.

가변 길이 슬라이딩 윈도우

• 윈도우의 크기를 필요에 따라 변경하면서 포인터를 이동시킵니다.
• 최소 길이 부분 배열이나 최대 길이 부분 배열을 찾는 문제에 활용합니다.

---

🏅 백준 1253번

🔗 문제 풀러가기

 

 

• 투 포인터로 푸는 문제인지 어떻게 알까?
  • 배열의 각 요소에 대해 좋은 수인지 확인해야 합니다.
  • 다른 수 두 개, 즉 두 개의 요소로 확인하므로 포인터 2개를 설정해야 하므로 투 포인터 알고리즘에 해당합니다.
• 포인터는 어떻게 이동해야 할까?
  • 자기 자신의 인덱스는 제외
  • 배열을 정렬 후 왼쪽 포인터는 가장 작은 값부터, 오른쪽 포인터는 가장 큰 값부터 출발합니다.
  • 두 포인터가 가리키는 요소의 합이 목표값보다 크면 오른쪽 포인터를 1 감소시키고, 작으면 왼쪽 포인터를 1 증가시킵니다.
    • 배열이 정렬된 상태라면 왼쪽 포인터를 1 증가시키면 더 큰 값을 더할 수 있고, 오른쪽 포인터를 1 감소시키면 더 작은 값을 더할 수 있기 때문입니다.
• 그 외 주의사항
  • 수의 개수는 최대 2000개로 for문을 돌려도 괜찮은 수입니다.
  • 요소의 값은 최대 1,000,000,000으로 long형을 사용합니다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        
        // 초기화
        int n = sc.nextInt();
        long[] arr = new long[n];
       	for(int i=0; i<n; i++)
        	arr[i] = sc.nextLong();
            
        // 정렬
        Arrays.sort(arr);
        
        int count = 0; //좋은 수의 개수
        // 순회하면서 좋은 수인지 확인
        for(int i=0; i<n; i++) {
        	int left = 0;	// 왼쪽 포인터는 가장 작은 값부터
            int right = n-1; 	// 오른쪽 포인터는 가장 큰 값부터
            
            while(left < right) {
            	// 자기 자신은 제외(다음 인덱스로 스킵)
                if(left==i || right==i) {
                	if(left==i) left++;
                    else right--;
                    continue; 
                }
                
                // 더한 값 확인
                long sum = arr[left] + arr[right];
                if(sum == arr[i]) {
                	count++;
                    break;
                } else if(sum > arr[i]) {
                	// 합이 더 크다면 더 작은 수를 더해야함 -> right를 한 칸 앞으로
                    right--;
                } else if(sum < arr[i]) {
                	// 합이 작다면 더 큰 수를 더해야함 -> left를 한 칸 뒤로
                    left++;
                }
            }
        }
        System.out.println(count);
    }
}

---

참고자료

[Java/알고리즘] 투 포인터 알고리즘(Two Pointer Algorithm) 이해하기 -1 : 종류, 활용방안