슬라이딩

이미 알거 같지만 한 번 더 질문을 해볼게요 !!

슬라이딩 유형은 미리 셋팅이 있어야 하는 것인가요??

또한

import java.util.*;

class Main {

    private int[] solution(int n, int m, int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int index = 0, lt = 0;
        int[] answer = new int[n - m + 1];
        while(lt < n - m + 1) {
            for (int rt = 0; rt < m; rt++) {
                map.put(arr[lt + rt], 1);

            }
            lt++;
            answer[index++] = map.size();
            map.clear();
        }
        
        return answer;
    }


    public static void main(String[] args){
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        for(int a : T.solution(n, m, arr)) {
            System.out.print(a + " ");
        }

    }
}

이렇게 풀면 시간 복잡도가 O(N^2) 이라서 시간 초과가 일어나는 것이죠 !?

안녕하세요, 인프런 AI 인턴입니다.

네, 맞습니다. 슬라이딩 윈도우 유형은 일반적으로 윈도우(범위)의 초기 설정을 해준 후, 윈도우의 시작점(lt)과 끝점(rt)을 슬라이딩하는 방식으로 문제를 해결합니다. 따라서 초기 설정 과정이 필요합니다.

해당 코드에서 solution 메서드 내부에 윈도우의 크기인 m에 따라 map에 값을 넣고, lt를 증가시키면서 매번 map을 초기화하고 있습니다. 이로 인해 while과 for 반복문이 중첩되어 사용되어 시간 복잡도가 O(N^2)이 되고, 큰 입력값이 주어질 경우 시간 초과가 발생할 수 있습니다.

슬라이딩 윈도우 기법을 효율적으로 사용하려면, 윈도우를 한 칸씩 슬라이딩하면서 윈도우에서 벗어나는 요소를 제거하고, 새롭게 윈도우에 포함되는 요소를 추가하는 방식으로 진행하여 시간 복잡도를 줄일 수 있습니다.

한 칸씩 윈도우를 옮길 때마다 새로운 요소의 카운트를 증가시키고, 윈도우에서 빠지는 요소의 카운트를 감소시켜 그 갯수를 관리하면서 윈도우 내의 요소 개수를 효율적으로 파악할 수 있게 됩니다. 이러한 방식을 적용하면 시간 복잡도를 O(N)까지 줄일 수 있습니다.

질문하신 슬라이딩 윈도우의 기본 원리와 효율적인 활용 방안을 이해하시는 데 도움이 되길 바랍니다.

인프런 커뮤니티 질문&답변