개념

• 슬라이딩 윈도우란?
  • “배열에서 연속된 K개의 요소의 최대 합을 구하라”
    • [ 1, 10, 3, 5, 4, 8, 7, 6, 2, 9]
  • 위 배열에서 단순하게 풀어보면 아래와 같이 모든 구간을 하나하나 계산해야한다.
    • 1, 10, 3 = 15
    • 10, 3, 5 = 18
    • 3, 5, 4 = 14
    • …
    • 6, 2, 9 = 17
  • 슬라이딩 윈도우는 이 문제를 효율적으로 활용할 수 있는 알고리즘이다.
• 어떤 문제를 해결할 때 유용한가? (예: 배열, 문자열 처리)
  • 이름의 그대로 창문을 밀면서 연산하는 방법을 사용한다.
  • 이 창문을 윈도우라고 말하겠다. 방법이 2가지가 있는데
  • 윈도우의 크기가 일정하게 2개씩 움직이는 경우에는 “고정 크기 윈도우”
  • 조건에 따라서 윈도우의 크기가 변하는걸 “가변 크기 윈도우” 라고 한다.
  • 핵심 원리는 이전 값을 재활용해서 연산을 줄이는 것임.
• 슬라이딩 윈도우의 장점
  • 시간 복잡도 개선
    • 위에서 언급한 배열에서 시간 복잡도는 O(N*K) 인데O(N)으로 줄어든다.
  • 불필요한 연산 최소화
    • 한 번 처리한 값을 다시 계산하지 않음.
• 코드 예제
  • 고정 크기 윈도우 예제 (예: 이동 평균, 최대값 찾기)
  • 가변 크기 윈도우 예제 (예: 부분합 문제)
• 다른 알고리즘 비교

• 문제 풀이 : 백준_12891

package BOJ12891;

import java.util.HashMap;
import java.util.Map;

public class BOJ12891 {

    public static int getCanMinhoMakePassword(String input, String str, String cnt) {

        // 파싱
        String[] in = input.split("\\\\s");
        int dnaStrLen = Integer.parseInt(in[0]);
        int bubunStrLen = Integer.parseInt(in[1]);

        String[] cntArray = cnt.split("\\\\s");
        Map<String, Integer> cntMap = new HashMap<>();
        cntMap.put("A", cntArray[0]); // 2
        cntMap.put("C", cntArray[1]); // 0
        cntMap.put("G", cntArray[2]); // 1
        cntMap.put("T", cntArray[3]); // 1

        Map<String, Integer> currentMap = new HashMap<>();
        currentMap.put("A", 0); // 1
        currentMap.put("C", 0); // 2
        currentMap.put("G", 0); // 3
        currentMap.put("T", 0); // 3

        // 문자 통계
        for (int i = 0; i < bubunStrLen; i++) {
            char c = str.charAt(i);
            currentMap.put(c, currentMap.getOrDefault(c, 0) + 1);
        }

        int answer = 0;
        for (char key : cntMap.keySet()) {
            if (currentMap.get(key) > cntMap.get(key)) {
                answer++;
            }
        }

        for (int i = bubunStrLen; i < dnaStrLen; i++) {
            char newChar = str.charAt(i); // 추가할거
            char oldChar = str.charAt(i - bubunStrLen); // 뺄거
            currentMap.put(newChar, currentMap.getOrDefault(newChar, 0) + 1);
            currentMap.put(oldChar, currentMap.get(oldChar) - 1);
            
            for (char key : cntMap.keySet()) {
                if (currentMap.get(key) > cntMap.get(key)) {
                    answer++;
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {

        String dnaInput = "9 8";
        String dnaStrByMinho = "CCTGGATTG";
        String dnaMinCnt = "2 0 1 1"; // A = 2, C = 0, G = 1, T =1

        int answer = getCanMinhoMakePassword(dnaInput, dnaStrByMinho, dnaMinCnt);
        if (answer = 0) {
            System.out.println("correct");
        } else {
            System.out.println("incorrect");
        }
    }
}
// DNA 문자열 : {‘A’, ‘C’, ‘G’, ‘T’}
// ACKA는 DNA 문자열 X
// ACCA는 DNA 문자열 O
// 버그 리포팅
// 부분 문자열을 뽑으면 AAAA와 같이 보안에 취약한 비밀번호 만들어짐
// 해결
// 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용가능