[JAVA] 알고리즘 : Hash, sliding window - 매출액의 종류

import java.util.*;

class Main {

    public ArrayList<Integer> solution(int n, int k, int[] arr) {
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> HM = new HashMap<>();

        for(int i=0; i<k-1; i++){
            HM.put(arr[i], HM.getOrDefault(arr[i], 0)+1);
        }
        int lt=0;
        for(int rt=k-1; rt<n; rt++){
            HM.put(arr[rt], HM.getOrDefault(arr[rt], 0)+1);
            answer.add(HM.size());
            HM.put(arr[lt], HM.get(arr[lt])-1);
            if(HM.get(arr[lt])==0) HM.remove(arr[lt]);
            lt++;
        }

        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        for (int x : T.solution(n, k, arr)) System.out.print(x + " ");

    }
}

 

 

k가 4라고 해보자.

k-1인 3개까지만 HashMap으로 키(숫자)와 값(숫자의 개수)를 세팅한다.

 

lt는 0, rt는 인덱스가 3인 네번째 원소부터 시작해 인덱스 rt의 키와 값을  hashMap에 추가한다. 

그리고 answer에 hashMap의 사이즈를 추가한다.

sliding window로 rt가 증가해 hashMap에 추가될 때마다 lt가 인덱스인 키의 값을 하나씩 감소시킨다.

 

이 때 주의해야할 점은 감소시키는 lt의 값이 0이 되면 hashMap에서 제거해줘야 한다.