03. Two Pointer Algorithm & Sliding Window

일반적으로 Two Pointer Algorithm은 2중 반복문을 통해 탐색해야하는 O(n^2) 코드를 O(n)으로 개선하는데 많이 사용된다.

해당 알고리즘은 '이동평균 구하기', '서로 다른 정렬된 배열의 요소값 합치기', '부분수열 탐색' 문제 등에서 사용될 수 있다.

 

아래는 Two Pointer Algoritm을 사용하는 대표적인 문제인 '요소값들의 합이 특정 값이 되는 연속 부분수열 구하기' 문제의 코드이다.

 

맨 처음 lt와 rt를 0번 인덱스로 초기화 해준다. 이후 lt~rt 사이의 요소값들의 합이 특정 값이 되는지 확인하면서 조건에 따라 lt와 rt값을 변화시킨 직후 lt와 rt 사이 요소값들의 합이 특정 값을 만족하는 경우 ans 변수를 1씩 카운트 해준다. 여기서 포인트는 rt값의 이동을 중심으로 반복문을 돌리되 lt 값을 한번에 옮기는 조건이다. lt~rt 사이의 값들의 합이 주어진 특정 값을 초과하는 경우 아무리 rt를 뒤로 옮긴다 하더라도 요소값들의 총합이 증가만 할 뿐 특정 값을 만족할 수 없다. 따라서 요소값들의 총합이 특정 값보다 초과하는 경우에는 총합이 더 작아질 때까지  lt값을 뒤로 옮긴다.

 

import java.util.Arrays;
import java.util.Scanner;

public class ContinuousSubSequential {
    public int solution(int size, int num, int[] arr){
        int ans=0, tmp=0, lt=0;
        for(int rt=0; rt<size; rt++){
            tmp+=arr[rt];
            while(tmp>num){
                tmp-=arr[lt++];
            }
            if(tmp==num) ans++;
        }
        return ans;
    }

    public static void main(String[] args) {
        ContinuousSubSequential t = new ContinuousSubSequential();
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int num = Integer.parseInt(sc.nextLine().substring(1));	
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(x->Integer.parseInt(x)).toArray(); // 입력값은 양의 정수만으로 이루어져 있다.
        System.out.println(t.solution(size,num,arr));
    }
}

 

 

 

Sliding Window는 한 배열에 저장되어 있는 연속된 요소값들에 대해서 요소값들의 최대 합, 혹은 조건을 만족하는 요소값들의 최대 길이 등의 문제를 풀어야 할 때 사용할 수 있다. 

 

아래는 주어진 배열에서 연속된 요소 값들의 합 중 주어진 길이를 만족하는 최대 합을 찾는 Sliding Window의 대표적인 문제인 '이동평균' 문제의 코드이다.

0번 인덱스부터 주어진 길이까지의 요소값을 합해서 초기 합에 대한 변수를 초기화 시켜주고 이후에는 맨 앞 인덱스 요소 값은 빼주고 뒤에 새로 추가되는 인덱스 값은 더해주면서 합이 최댓값인지 탐색한다. 

import java.util.Arrays;
import java.util.Scanner;

public class MaxIncome {
    public int solution(int n, int k, int[] arr){
        int ans=0, tmp=0;
        for(int i=0; i<k; i++){
            tmp += arr[i];
        }
        ans = tmp;
        for(int i=k; i<n; i++){
            tmp+=arr[i]-arr[i-k];
            ans = Math.max(ans,tmp);
        }
        return ans;
    }
    public static void main(String[] args) {
        MaxIncome t = new MaxIncome();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = Integer.parseInt(sc.nextLine().substring(1));
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(x->Integer.parseInt(x)).toArray();
        System.out.println(t.solution(n,k,arr));
    }
}

---

참고 레퍼런스

• https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard