[코딩테스트] two pointer technique / 투 포인터 기법

two pointer technique

• 배열이나 리스트와 같은 선형 구조에서 두 개의 점(포인터)를 이용하여 원하는 조건을 만족하는 부분 구조를 효율적으로 찾아내는 알고리즘 기법
• 특정 합을 만족하는 두 수를 찾거나 부분 배열의 최소 길이를 찾는 문제 등에 활용

같은 방향으로 이동

• 보통 right 포인터가 먼저 조건을 만족할 때까지 이동하고 조건을 만족하는 상태에서 left 포인터를 이동시키면서 조건을 유지할 수 있는 최소, 최대 범위를 찾음
• 연속된 부분 구조를 찾는 문제에 적용

sum은 1 → 4가 됨

public static int solution(int[] arr, int x) {
		int count = 0;
		int sum = 0;
		int left = 0;
		int right = 0;

		while(left < arr.length) {
			if(sum == x) {
				count++;
				sum -= arr[left];
				left++;
			} else if(sum < x) {
				sum += arr[right];
				right++;
			} else if(sum > x) {
				sum -= arr[left];
				left++;
			}
		}
		return count;
	}

• 두 원소의 합과 x가 같으면 arr[left]를 빼서 초기화 시켜주고, 다시 left 하나 이동
• 맨 처음 시작할 때 left, right = 0으로 sum < x 조건에 부합하여 sum = 1, right = 1이 됨

반대 방향으로 이동

• 두 포인터가 서로를 향해 이동하면서 조건을 만족하는 경우를 찾음
• 대부분 정렬된 배열이나 리스트에서 사용

public static int[] solution(int[] arr, int x) {
		int left = 0;
		int right = arr.length-1;
		int []answer;

		while(left < right ) {
			int sum = arr[left] + arr[right];
			if(sum == x) {
				 return new int[]{left, right};
			} else if(sum < x) {
				left++;
			} else if(sum > x){
				right--;
			}
		}
		return new int[]{-1, -1};
	}

---

탐욕법 (greedy) 문제 - 투 포인터 사용

• 순간 최적의 해결책을 선택함으로써 최종적인 해답에 도달하는 방법

예시

1. 동전 거스름돈 문제: 가장 큰 단위의 동전부터 차례대로 거슬러 줌으로써 필요한 동전의 수를 최소화하는 문제입니다.
2. 분할 가능 배낭 문제(Knapsack Problem): 물건을 쪼갤 수 있을 때, 가방에 넣을 수 있는 물건의 가치를 최대화하는 문제입니다. 가치 대비 무게가 가장 큰 물건부터 선택합니다.
3. 활동 선택 문제(Activity Selection Problem): 시작 시간과 끝나는 시간이 주어진 활동들 중 서로 겹치지 않고 최대한 많이 선택하는 문제입니다. 끝나는 시간이 가장 빠른 활동부터 선택합니다.

•  

https://school.programmers.co.kr/learn/courses/30/lessons/42885#

프로그래머스

• 반대 방향으로 이동하는 투 포인터를 사용
• 정렬 후, sum이 초과되면 count++, right-- 오른쪽 포인터만 이동
• sum이 같거나 작으면 count++, right--, left++ 포인터 둘 다 이동
• left == right 조건일 때 마지막으로 count++