[알고리즘] 투 포인터와 슬라이딩 윈도우 (Java)
투 포인터
투 포인터는 주어진 배열에서 두 개의 포인터를 조작해가며 원하는 것을 얻는 기법이다.
투 포인터 알고리즘 문제 유형
- 포인터 2개가 같은 방향으로 진행
- 포인터 2개가 양끝에서 시작하여 반대로 진행
1. 포인터 2개가 같은 방향으로 진행
백준 2003번: 수들의 합2 해당 문제 예제 2번을 통해 시뮬레이션을 돌려보자.
n = 10, m=5, 원소의 갯수가 10개인 배열에서 구간 합이 5인 구간을 찾으면 된다. 빨간색은 s이고, 파란색은 e인 두 포인터는 시작점 0에서 같이 탐색을 시작한다.
e를 한 칸씩 움직여 s~e사이에 있는 원소들의 구간합을 구한다. sum :1
sum의 값이 m보다 크게 될 경우 e의 값을 조정하면 값이 더욱 커지기 때문에 s의 값을 이동해서 앞에 있는 원소들을 하나씩 빼준다. sum = 6 - 1(arr[s])
그러면 sum==m이 되므로 해당 구간에서 카운트를 해주면 된다.
이와 같은 방식으로 계속 탐색을 해나가면 된다.
e의 포인터가 배열의 끝(n)에 도착했을 때 이제 여기서 두 가지의 경우로 나누어진다.
- 만약 sum>= m이면 아직 탐색할 구간이 남았으므로 s의 값을 이동해주면서 구간 탐색을 더해준다.
- 만약 sum<m이면 더 이상 탐색해봤자 sum보다 큰 값은 안나오므로 반복문을 종료해주면 된다.
풀이 코드
import java.io.*;
public class Main {
public static void main(String[] args){
int[] arr = new int[] {1, 2, 3, 4, 2, 5, 3, 1, 1, 2};
int n=10, m = 5;
// s,e 투 포인터가 같이 0에서 오른쪽 방향으로 이동하며 탐색
int s=0, e=0, sum=0, cnt=0;
while(true) {
if(sum>=m) {
sum -= arr[s++];
}else if(e==n) break;
else {
sum += arr[e++];
}
if(sum==m) {
cnt++;
}
}
System.out.println(cnt);
}
}2. 포인터 2개가 양끝에서 시작하여 반대로 진행
백준 2470번: 두 용액 해당 문제의 예제를 통해 시뮬레이션을 돌려보자.
n=5, 원소의 갯수가 5개인 배열에서 0에 가장 가까운 용액을 만들어 내는 추출해줘야 하기 때문에 먼저 배열을 정렬해준 후, 양쪽 끝에서 두 포인터를 이용하여 서로 중앙을 향해 거리를 좁혀지는 형태로 진행하면서 용액을 골라내주면 된다. 두 개 이상일 경우에는 아무거나 추출해주면 된다.
빨간색은 s이고, 파란색은 e인 두 포인터는 s는 맨 왼쪽 0에서 시작하고 e는 배열의 끝 n에서 탐색을 시작한다. arr[s]+arr[e]의 값을 구한 다음 0과 가까운 값을 구하면 된다.
arr[s]+arr[e] = -92 < 0 이므로 값이 더 커져야한다. 해당 배열은 오름차순으로 정렬했기 때문에 두 수의 합이 커지기 위해서 s의 포인터를 한 칸 움직여줘서 더 큰 값을 넣어준다.
arr[s]+arr[e] = 5 > 0 이므로 값이 더 작아져야 한다. 작은 값을 넣어주기 위해서는 e의 포인터를 움직여준다.
arr[s]+arr[e] = 2 > 0 이므로 값이 더 작아져야 하므로 위와 같이 e의 포인터를 움직여준다.
arr[s]+arr[e] = -3 < 0 이므로 이번엔 s를 움직여주자.
그런데 start >= end이므로 더 이상 탐색이 불가능하므로 종료해준다.
☛ 답은 가장 0에 가까웠던 2로, 해당 구간에 속하는 두 용액 -2, 4가 된다.
import java.io.*;
import java.util.Arrays;
public class Main {
public static void main(String[] args){
int n =5;
int[] arr= new int[] {-99, -2, -1, 4, 7};
Arrays.sort(arr);
int[] res = new int[2];
// s,e 투 포인터가 각 양쪽 끝에서 가운데 방향으로 탐색
int s=0, e=n-1, min=Integer.MAX_VALUE;
while(s < e) {
int sum = arr[s]+arr[e];
if(min> Math.abs(sum)) {
min = Math.abs(sum);
res[0] = arr[s];
res[1] = arr[e];
if(sum==0) break;
}
if(sum <0) s++;
else e--;
}
System.out.println(res[0]+" "+res[1]);
}
}
슬라이딩 윈도우
슬라이딩 윈도우는 투 포인터와 비슷한 유형이다.
투 포인터와의 차이점
투포인터와 다른점이 있다면 투 포인터 알고리즘은 구간의 길이를 가변적으로 잡기 때문에 구간의 양쪽 끝이 되는 포인터가 2개 필요하다.
반면에, 슬라이딩 윈도우 알고리즘은 어느 순간에도 구간의 길이를 고정적으로 잡기 때문에 포인터가 2개일 필요가 없다. 언제나 구간의 넓이가 동일하기 때문에 포인터 하나만 있어도 그 고정적인 길이를 알고 있으므로 끝이 어딘지 알 수 있기 때문이다.
1. 최솟값 찾기
백준 11003번: 최솟값 찾기 해당 문제 예제 2번을 통해 시뮬레이션을 돌려보자.
예제) 12 3
1 5 2 3 6 2 3 7 3 5 2 6
원소의 갯수가 12개인 배열과 창문의 너비는 3인 조건을 갖고 탐색하면서 창문의 구간에 해당하는 최솟값을 찾아주면 된다.
구간의 고정 길이를(즉 창문의 너비를) L 이라고 할 때 창문을 한 칸 옮기더라도 옮기기 전 창문 안에 있던 L-1 칸은 겹치게 된다.
- 기존 모습 : ⬜️🟦🟦🟦🟦⬜️⬜️
- 다음 모습 : ⬜️⬜️🟦🟦🟦🟦⬜️
기존 구간과 새 구간의 ⬜️🟦🟪🟪🟪🟦⬜️ 보라색 부분은 겹치게 된다. 보라색 부분은 새 구간에도 포함이 되어 있으므로 새 구간에서는 빠지게 된 앞의 🟦 와 새 구간에 포함되게 된 🟦 만 비교하게 되면 더 효율적일 것이다. 시간복잡도 O(N^2)를 피할 수 있다.
탐색 과정
Deque안의 값은 int[] 배열로 첫 번째 인자에는 데이터를 넣어주고 두 번째에는 인덱스를 넣어주었다.
i=0 : [ {1,0} ] ☛ bw.write : 1
i=1 : [ {1,0}, {5,1} ] ☛ bw.write : 1 1
i=2 : [ {1,0}, {5,1}, {2,2} ] ☛ bw.write : 1 1 1
→ 새로 들어오는 값보다 이전의 값이 더 크다면 값을 빼준다. (5>2 : q.peekLast()[0] > num)
i=3 : [ {1,0}, {2,2}, {3,3} ] ☛ bw.write : 1 1 1 2
→ 현재 최솟값의 인덱스가 창문의 너비 값을 벗어나면 삭제해준다. (0 < 1 : q.peek()[1] < i -(l-1))
i=4 : [ {2,2}, {3,3}, {6,4} ] ☛ bw.write : 1 1 1 2 2
i=5 : [ {2,2}, {3,3}, {6,4}, {2,5} ] ☛ bw.write : 1 1 1 2 2 2
→ 새로 들어오는 값보다 이전의 값이 더 크다면 값을 빼준다. (3,6 > 2 : q.peekLast()[0] > num)
→ 현재 최솟값의 인덱스가 창문의 너비 값을 벗어나면 삭제해준다. (2 < 3 : q.peek()[1] < i -(l-1))
i=6 : [ {2,5}, {3,6} ] ☛ bw.write : 1 1 1 2 2 2 2
i=7 : [ {2,5}, {3,6}, {7,7} ] ☛ bw.write : 1 1 1 2 2 2 2 2
i=8 : [ {2,5}, {3,6}, {7,7}, {3,8} ] ☛ bw.write : 1 1 1 2 2 2 2 2 3
→ 새로 들어오는 값보다 이전의 값이 더 크다면 값을 빼준다. (7 > 3 : q.peekLast()[0] > num)
→ 현재 최솟값의 인덱스가 창문의 너비 값을 벗어나면 삭제해준다. (5 < 6 : q.peek()[1] < i -(l-1))
i=9 : [ {3,6}, {3,8}, {5,9} ] ☛ bw.write : 1 1 1 2 2 2 2 2 3 3
i=10 : [ {3,6}, {3,8}, {5,9}, {2,10} ] ☛ bw.write : 1 1 1 2 2 2 2 2 3 3 2
→ 새로 들어오는 값보다 이전의 값이 더 크다면 값을 빼준다. (3,5 > 2 : q.peekLast()[0] > num)
i=11 : [ {2,10}, {3,11} ] ☛ bw.write : 1 1 1 2 2 2 2 2 3 3 2 2
풀이 코드
양방향 큐인 Deque를 사용하여 풀이하였다. 우선순위 큐를 사용해도 되지만 Java로는 해당 문제의 시간 제한에 통과하기가 어렵다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int l = Integer.parseInt(st.nextToken());
Deque<int[]> q = new ArrayDeque<>();
st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) {
int num = Integer.parseInt(st.nextToken());
while(!q.isEmpty() && q.peekLast()[0] > num) q.pollLast();
q.offer(new int[] {num,i});
if(q.peek()[1] < i -(l-1)) {
q.poll();
}
bw.write(q.peek()[0]+" ");
}
bw.flush();
bw.close();
}
}
투 포인터, 슬라이딩 윈도우 알고리즘 시간복잡도
매 루프마다 항상 2개의 포인터 중 하나는 1씩 증가하고 있고, 각 포인터가 N번 누적 증가해야 알고리즘이 끝난다. 따라서 투 포인터의 시간복잡도는 O(N)이다.
슬라이딩 윈도우 또한 구간 N에서 삽입O(1),삭제O(1)를 반복하기 때문에 시간복잡도는 O(N)이다.
다른 슬라이딩 윈도우 문제 풀러가기
백준 2075번: N번째 큰 수 ☛ 문제 풀이 보러가기