슬라이딩 윈도우 관련 문제 모음!

WOOK JONG KIM·2023년 4월 3일

코딩테스트_문제모음집

코테문제_모음집

목록 보기

4/12

슬라이딩 윈도우

문제 1

https://www.acmicpc.net/problem/12891

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        String pw = br.readLine();
        char[] pwArr = pw.toCharArray();
        st = new StringTokenizer(br.readLine());

        final int aCount = Integer.parseInt(st.nextToken());
        final int cCount = Integer.parseInt(st.nextToken());
        final int gCount = Integer.parseInt(st.nextToken());
        final int tCount = Integer.parseInt(st.nextToken());

        int answer = 0;

        for(int i = 0; i <= N-M; i++){
            int startIndex = i; int endIndex = (i+M)-1;
            int aCnt = aCount; int cCnt = cCount;
            int gCnt = gCount; int tCnt = tCount;

            while(startIndex <= endIndex){
                if(pwArr[endIndex] == 'C'){
                    cCnt--; endIndex--;
                }else if(pwArr[endIndex] == 'A'){
                    aCnt--; endIndex--;
                }else if(pwArr[endIndex] == 'G'){
                    gCnt--; endIndex--;
                }else{
                    tCnt--; endIndex--;
                }
            }

            boolean isGood = true;
            if(aCnt > 0 || cCnt > 0 || gCnt > 0 || tCnt > 0){
                isGood = false;
            }

            if(isGood){
                answer++;
            }
        }
        System.out.println(answer);
    }
}

처음에 위에 처럼 생각없이 써버렸다.. 당연히 시간초과

이 코드의 시간 복잡도는 O(N) + O((N-M) * M)

슬라이딩 윈도우를 사용이해하기
-> 위에 그림 예시에서 보이는 초록색 부분이 부분 패스워드의 길이, 전체가 패스워드의 길이
-> 부분 패스의 크기만큼 윈도우를 지정하여 전체 패스워드 길이에 시작점에 둠
-> 그다음 윈도우를 오른쪽으로 밀면서 윈도우에 잡힌 값들이 조건에 맞는지 확인

문제 1 푸는 아이디어

전체 패스워드에 대한 배열과, 비밀번호 체크 배열을 저장

ex) S 배열 -> CCTGGATTG
비밀번호 체크 배열:
ACGT(2011)
윈도우에 포함된 문자로 현재 상태의 배열을 만듬. 그런 다음 현재 상태 배열과 비밀번호 체크 배열을 비교하여 유효 비밀번호 인지 판단
배열 현재 상태 (CCTGGATT)G
현재 상태 배열 ACGT(1223) 비밀번호 체크 배열 ACGT(2011)
-> 비밀번호 체크 배열보다 현재 상태 배열에 A가 더 적으므로 유효한 비밀번호 X
윈도우를 한칸씩 이동하며 현재 상태 배열을 업데이트, 현재 상태 배열을 업데이트 한 이후에는 비밀번호 체크 배열과 비교하여 비밀번호 유효성을 판단
-> 이때 현재 상태의 배열을 업데이트 할때는 , 신규 문자열만 보고 업데이트 하는 방식으로 진행!!!
-> C(CTGGATTG) -> 아까의 배열 상태와 비교했을 때 C가 한개 제거되고, G가 한개 추가됨
-> (1,2-1,2+1,3)

해결 코드

import java.io.*;
import java.util.*;

public class Main {

    static int checkArr[];
    static int myArr[];
    static int checkSecret;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken()); // 문자열의 크기
        int P = Integer.parseInt(st.nextToken()); // 부분 문자열의 크기
        int Result = 0;
        char A[] = new char[S];
        checkArr = new int[4]; myArr = new int[4];// 비밀번호 체크 배열 및 현재 상태 배열
        checkSecret = 0; // 몇개의 문자와 관련된 개수를 충족했는지 판단

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

        for(int i = 0; i < P; i++){
            // 초기 P문자열 처리
            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);
        br.close();
    }

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

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