투포인터

리스트에서 두 개의 포인터가 가리키는 값을 뽑아 연산하는데 쓰인다.

---

투포인터를 알고 저번 학기에 들었던 전공에서 해당 내용을 배웠던게 생각나서 반가웠다.

위 그림처럼 두 배열이 있고, 두 배열을 원소의 중복없이 합치고 싶을 때 어떻게 해야할까? 우선 위의 배열에서 하나를 선택하고(arr1_length = x) 아래 배열을 순차적으로 탐색해(arr2_length = y) 동일한 원소가 있을 때를 처리하면 된다. 이때 발생하는 비용은 몇 개를 선택하는지, 그 하나는 몇 번을 탐색하는지에 달려있으므로 $arr1\_length\times arr2\_length$ 이다. $\Rightarrow O(xy)$

그럼 위 그림처럼 오름차순으로 정렬된 두 배열이 있고 두 배열을 원소의 중복없이 합치고 싶을 때 어떻게 해야할까? 우선 하나의 포인터는 위 배열의 첫번째 원소를 가리키고, 나머지 포인터는 아래 배열의 첫번째 원소를 가리킨다고 하자.
1. 만약 현재 두 포인터가 가리키고 있는 값이 $point1\_value > point2\_value$ 라면, point1.value를 새 배열에 넣고 point1의 위치를 한 칸 뒤로 당긴다.
2. 만약 $point1\_value < point2\_value$ 라면, point2.value를 새 배열에 넣고 point2의 위치를 한 칸 뒤로 당긴다.
3. 만약 $point1\_value = point2\_value$ 라면 두 배열이 중복된 원소가지므로 point1 또는 point2의 값 하나만 새 배열에 넣고 point1, 2를 모두 뒤로 이동시킨다.

point1, 2 둘 중 하나가 마지막 원소를 넘어선 인덱스를 참조할 때까지 위 과정을 반복하고, 남은 나머지 원소들을 새 배열에 추가하면 된다. 이때 발생하는 비용은 $arr1\_length+arr2\_length$ 이다. 위 방법과 비교해서 확연하게 차이가 남을 알 수 있다. $\Rightarrow O(x+y)$

이렇게 두 포인터의 위치를 바꾸며 답을 구하고, 계산시간은 짧게 하는 것이 투포인터의 장점이다. 투포인터는 하나의 배열에서도 사용할 수 있으며, 위 예제에서도 보았듯이 포인터의 방향성이 중요하기 때문에 사용되는 리스트(배열)는 꼭 정렬된 상태여야 한다.

예제

불연속적인 위치들의 수를 뽑아 특정 조건을 만족하는 개수 구하기

백준 2470 두 용액 - [풀이]

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 
각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  
산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 
알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 
이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 
특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 
이 용액이 특성값이 0에 가장 가까운 용액이다. 
참고로, 두 종류의 알칼리성 용액만으로나 
혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 
이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

• 용액 2개를 뽑아 모든 조합을 만들어 비교하는 방식은 시간 비용이 많이 든다. ($n^2$)
• 만약 용액 리스트가 정렬되어 있다면, 투포인터를 이용해 두 용액의 합을 보고 포인터를 이동시켜 답을 구할 수 있다.
  - 정렬 비용은 $n\log n$ 이므로 입력받은 용액 리스트를 정렬한다.
  - 두 개의 포인터는 처음에 1번째 용액과 마지막 용액을 가리키고 있다. 만약 두 용액의 합이 이전에 나온 합보다 작다고 판단되면 그 용액 값과 최소값을 저장한다.
  - 이제 두 포인터를 어떤 조건을 통해 이동해야 할지 살펴봐야 한다. 만약 두 용액의 합이 양수값이라면 둘 중 큰 용액을 가리키는 (right)포인터를 앞으로 당긴다. 음수값이라면 둘 중 작은 용액을 가리키는 (left)포인터를 뒤로 민다.
  eg) [-10 -5 3 7] => (-10, 7) = (-3) => (-5 7) = (2) => (-5, 3) = (-2) => right<left... answer:2

연속적인 위치들의 수를 포함해 특정 조건을 만족하는 구간 구하기 [슬라이딩 윈도우]

CosPro 기출 3회 - 문제9번 팝업스토어

모 매장에서는 팝업스토어를 열려고 합니다. 팝업스토어란 한정 기간 문을 여는 매장입니다. 
팝업스토어는 k일 동안 연속해서 열 예정입니다. 
n일 동안의 추정 매출액이 주어질 때, 언제 팝업스토어를 열어야 가장 매출이 높을지 알아보려 합니다.

n일 간의 추정 매출액이 담긴 배열 revenue와 팝업스토어를 열 날의 수 k가 매개변수로 주어질 때,
최대 매출액 합을 return 하도록 solution 메소드를 작성했습니다...

• 연속적인 범위가 중요한 문제로, 일반적인 투포인터와 다르게 두 개의 포인터가 필요없다. (하나의 포인터만 알아도 범위는 지정되어 있기 때문에 다음 포인터를 알고 있다.) 이를 슬라이딩 윈도우 알고리즘으로 풀 수 있다.
• 첫번째 날부터 k번째 날까지 하나씩 먼저 합(sum)을 구한다. 이로써 범위가 픽스된다.
• 두번째 날부터 K+1번째 날까지 (총 k일) 합을 구하는데, 앞서 하나씩 더한 방식을 사용하지 않는다. 2번째~k번째 날까지는 sum에 연산되어 있고, sum에서 첫번째 날만 빼고 K+1번째 날의 매출액을 더하면 두번째 날부터 K+1번째 날까지의 합이 되기 때문이다! 이것이 슬라이딩 윈도우의 핵심이다.
• 첫날을 기준으로 k번 더하기 연산, 기준날을 바꾸는데 n-k+1번 걸린다. 따라서 시간 비용은 $O(n)$ 이다.

초록색 : 이미 연산된 부분.
노란색 : 이미 연산된 부분에서 빼야할 부분.
파란색 : 이미 연산된 부분에서 추가해서 더해야 할 부분.

public int solution(int[] revenue, int k) {
	int answer = 0;
	int n = revenue.length;
	int sum = 0;
	for (int i = 0; i < k; i++) {
		sum += revenue[i];
	}
	answer = sum;
	for (int i = k; i < n; i++) {
		sum = sum - revenue[i - k] + revenue[i];
		if (answer < sum)
			answer = sum;
	}
	return answer;
}