[알고리즘] Two pointers, Sliding window

투포인터(Two Pointers)

투포인터란?

리스트에 순차적으로 접근해야 할 때 두개의 포인터를 기록하면서 처리하는 알고리즘입니다.
투포인터 알고리즘을 사용하는 문제를 풀어봅시다.

문제 - 공통 원소 구하기

A, B의 배열이 주어지면 공통된 원소를 구해서 반환하세요.

제한사항

• A의 크기 ( 1 <= N <= 30,000)
• B의 크기 ( 1 <= M <= 30,000)
• 각 집합의 원소는 1,000,000,000 이하의 자연수입니다.

출력설명

• 두 집합의 공통원소를 오름차순 정렬하여 반환합니다.

입력예제

int[] a = {1,3,9,5,2};
int[] b = {3,2,5,7,8};

출력예제

{2,3,5}

풀이

    public static List<Integer> solution(int[] a, int[] b) {
        // step 1.
        Arrays.sort(a); 
        Arrays.sort(b);
        
        int p1 = 0;
        int p2 = 0;
        List<Integer> answerList = new ArrayList<>();
        
        //step 2.
        while(p1 < a.length && p2 < b.length) {
            if(a[p1] == b[p2]) { //step 2-1
                answerList.add(a[p1]);
                p1++;
                p2++;
            }else if(a[p1] > b[p2]) { //step 2-2
                p2++;
            }else{ //step 2-3
                p1++;
            }
        }
        
        return answerList;
    }

• step1 : 두 배열을 모두 오름차순 정렬을 해줍니다.
• step2 : 두개의 포인터가 각자의 배열의 길이보다 작을경우 수행되는 while문을 실행시킵니다.
• step2-1 : 두 배열에서 각자의 포인터에 값이 같을 경우 공통원소이므로 answerList에 추가시켜준 후 p1, p2 모두 1씩 증가시켜줍니다.
• step2-2 : 값이 다르고 a배열에 있는 값이 클 경우 b배열에서 사용하는 포인터 변수 (p2)만 1증가시켜줍니다.
• step2-3 : 값이 다르고 b배열에 있는 값이 클 경우 a배열에서 사용하는 포인터 변수(p1)만 1증가시켜줍니다.

p1, p2둘중 하나라도 각 배열의 길이보다 커질 시 while문은 종료가 되며 공통된 원소의 리스트가 완성됩니다.

시간복잡도는 O(N)입니다.

Sliding Window(슬라이딩 윈도우)

Sliding Window란?

Two pointers처럼 구간을 훑으면서 지나간다는 공통점이 있으나 슬라이딩 윈도우는 어느 순간에도 구간의 넓이가 동일하다는 차이점이 있습니다.

아래 문제를 풀면서 이해해봅시다.

문제 - 최대 매출

N일 동안의 매출기록이 저장되어 있는 배열 arr이 주어지면 이 중 에서 연속된 K일 동안의 최대 매출액이 얼마인지 구하시오.

제한사항

• N의 크기 ( 5 <= N <= 100,000)
• K의 크기 ( 2 <= K <= N)
• 매출기록의 숫자들은 500이하의 음이 아닌 정수입니다.

출력설명

• 최대 매출액을 구하세요.

입력예제

int[] arr = {12, 15, 11, 20, 25, 10, 20, 19, 13, 15};
int k = 3;

출력예제

56

풀이

public static int solution(int[] arr, int k){
        int currSum = 0; // 현재 구간의 합계
        
        //step 1.
        for(int i = 0; i < k; i++){
            currSum += arr[i];
        }
        
        //step 2.
        int maxSum = currSum;
        int lt = 1;
        int rt = lt + k - 1;
        
        //step 3.
        while(rt < arr.length){
        	//step 3-1
            currSum -= arr[lt- 1];
            currSum += arr[rt];
            
            //step 3-2
            maxSum = Math.max(maxSum, currSum);
            
            //step 3-3
            lt++;
            rt++;
        }
        
        return maxSum;
    }

• step1 : currSum에 처음구간인 첫번째부터 k번째 구간의 합계를 저장시켜줍니다.
• step2 : maxSum에 첫 구간의 합계를 넣어주고 포인터변수 lt, rt의 값을 초기화시켜줍니다. ( k가 3일경우 lt = 1, rt = 3 )
• step3 : 오른쪽 포인터변수 rt가 배열의 길이보다 작을경우까지 while문을 돌려줍니다.
• step3-1 : currSum에 이전 구간의 첫번째 값 (예를들어 lt가 1 rt가 3일경우 이전 구간의 첫번째 값은 arr[0] 즉 arr[lt-1]값을 빼줍니다. 그리고 현재 rt위치의 매출을 더해줍니다.
• step3-2 : maxSum과 currSum중 큰값을 maxSum에 넣어줍니다.
• step3-3 : 다음 구간을 진입하기 위해 lt, rt모두 1씩 더해줍니다.

투포인터와 동일하게 시간복잡도는 O(N)입니다.

코딩테스트 문제에 가끔 등장하는 알고리즘이므로 모두 알아둡시다!!