구간 합 / 투 포인터 / 슬라이딩 윈도우

1. 구간 합

: 합 배열을 이용해 시간 복잡도를 줄이는 알고리즘

: O(1)

: Sum[i] = Sum[i-1] + Arr[i] 공식

 

 

구간합 기본 구현 로직

    void test3() {
        int arr[] = {15, 13, 10, 7, 3, 12}; // 예시
        int sumArr[] = new int[arr.length]; // 합 배열


        // 합 배열 알고리즘
        // Sum[i] = Sum[i-1] + Arr[i]
        sumArr[0] = arr[0];
        for(int i=1; i<arr.length; i++) {
            sumArr[i] = sumArr[i-1] + arr[i];
        }

        for(int i=0; i<sumArr.length; i++) {
            System.out.println(sumArr[i]);
        }

        // 구간합 구하기 : i ~ j까지
        // Sum[j] - Sum[i-1]
        // ex) 2~5 : sumArr[5] - sumArr[1]
        System.out.println(sumArr[5] - sumArr[1]);
    }

---

2. 투 포인터

: O(n)

 

 

백준 온라인 저지 2018번 : 대표적 투포인터 예제

import java.util.Scanner;

public class P2018_연속된자연수의합 {
    public static void start() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int count = 1;
        int start_idx = 1;
        int end_idx = 1;
        int sum = 1; // N일 경우

        while(end_idx < N) {
            if(sum == N) {
                count++;
                end_idx += 1;
                sum = sum + end_idx;

            } else if(sum < N) {
                end_idx += 1;
                sum = sum + end_idx;

            } else if(sum > N) {
                sum = sum - start_idx;
                start_idx += 1;
            }
        }

        System.out.println(count);
    }
}

 

15, 7+8, 4+5+6, 1+2+3+4+5 => 4가지

---

3. 슬라이딩 윈도우

: 2개의 포인터로 범위를 지정한 후, 범위를 유지한 채로 이동하며 해결 -> 마치 창틀에 창문을 놓고 이동하는 모양이어 '슬라이딩 윈도우'라고 부름

: 배열의 길이만큼만 탐색을 진행하면 되므로 시간복잡도는 O(n)

 

 

백준 온라인 저지 12891번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class P12891_DNA비밀번호 {
    static int myArr[];
    static int checkArr[];
    static int checkSecret; // 조건을 만족하는지 -> 총 4가 되면 만족

    public static void start() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int S = Integer.parseInt(st.nextToken());
        int P =Integer.parseInt(st.nextToken());
        int Result = 0;
        char A[] = new char[S];
        myArr = new int[4];
        checkArr = new int[4];
        checkSecret = 0;

        A = bf.readLine().toCharArray();
        st = new StringTokenizer(bf.readLine());
        for(int i=0; i<4; i++) {
            checkArr[i] = Integer.parseInt(st.nextToken());

            if(checkArr[i] == 0) {
                // 0이 입력되었다는건, 이미 조건 1개는 만족했다는 것과 같음
                checkSecret++;
            }
        }

        // 부분 문자열 처음 받았을 때 셋팅
        for(int i=0; i<P; i++) {
            Add(A[i]);
        }

        if(checkSecret == 4) {
            Result++;
        }

        // 슬라이딩 윈도우 시작!
        // 같은 범위로 한칸 오른쪽으로 갔을때, 맨 오른쪽 값을 추가해주고 맨 왼쪽 값을 빼주면 됨
        for(int i=P; i<S; i++) {
            int j = i-P;
            Add(A[i]); // 맨 오른쪽 값 하나 추가
            Remove(A[j]); // 맨 왼쪽 값 하나 제거
            
            if(checkSecret == 4) {
                Result++;
            }    
        }

        System.out.println(Result);
        bf.close();
    }

    private static void Remove(char c) {
        switch(c) {
            case 'A':
                if(checkArr[0] == myArr[0]) {
                    checkSecret--;
                }
                myArr[0]--;

                break;
            case 'C':
                if(checkArr[1] == myArr[1]) {
                    checkSecret--;
                }
                myArr[1]--;
                break;
            case 'G':
                if(checkArr[2] == myArr[2]) {
                    checkSecret--;
                }
                myArr[2]--;
                break;
            case 'T':
                if(checkArr[3] == myArr[3]) {
                    checkSecret++;
                }
                myArr[3]--;
                break;
        }
    }

    private static void Add(char c) {
        switch(c) {
            case 'A':
                myArr[0]++;
                if(checkArr[0] == myArr[0]) {
                    checkSecret++;
                }
                break;
            case 'C':
                myArr[1]++;
                if(checkArr[1] == myArr[1]) {
                    checkSecret++;
                }
                break;
            case 'G':
                myArr[2]++;
                if(checkArr[2] == myArr[2]) {
                    checkSecret++;
                }
                break;
            case 'T':
                myArr[3]++;
                if(checkArr[3] == myArr[3]) {
                    checkSecret++;
                }
                break;

        }
    }

}