Sliding Window, HashMap, Two Pointer_매출액의 종류

✅ N일 동안의 매출기록이 있고, K일 동안의 매출액 종류를 구간별로 구합니다.

예를 들어 N = 7, K = 4이면
첫 번째 구간은 [20, 12, 20, 10] 매출액 종류: 20, 12, 10 따라서 3
두 번째 구간은 [12, 20, 10, 23] 따라서 4
세 번째 구간은 [20, 10, 23, 17] 따라서 4
네 번째 구간은 [10, 23, 17, 10] 따라서 3

class Main {

    public ArrayList<Integer> solution(int n, int k, int[] intArr){
        ArrayList answerList= new ArrayList();
        HashMap<Integer, Integer> map= new HashMap<>();
        //first window, 1작게
        for(int i=0; i<k-1; i++){
            map.put(intArr[i], map.getOrDefault(intArr[i], 0)+1);
        }
        int lt=0;
        for(int rt=k-1; rt<n; rt++){
            map.put(intArr[rt], map.getOrDefault(intArr[rt], 0)+1);
            //add
            answerList.add(map.size());
            //sliding window
            map.put(intArr[lt], map.get(intArr[lt])-1);
            if(map.get(intArr[lt]) ==0) map.remove(intArr[lt]);
            lt++;
        }



        return answerList;
    }
    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[] intArr= new int[n];
        for(int i=0; i<n; i++){
            intArr[i] = sc.nextInt();
        }
        for(int x: T.solution(n, k, intArr)){
            System.out.print(x+ " ");
        }
    }
}
//⭐️input:
// 7 4
// 20 12 20 10 23 17 10
//⭐️output:
//3 4 4 3

🔵 ThingsILearned

1. 이 문제는 sliding window, two pointers, hashmap 을 모두 이용하는 문제이다.
   
2. 맨 처음 window를 원래 크기 4보다 하나 작게 잡는다. 크기를 3으로 잡는다.
   💡 그 이유는, 원래 sliding window에서는 원래 크기로 첫 번째 window로 잡고, 두 번째 window부터 다음꺼 하나 더하고, 맨 앞에 하나 빼기를 시작하지만,
   이번 문제의 경우 첫 번째 window부터 size 구해서 answerList에 추가하기 위함.
   
3. 먼저 window다음에 오는 값을 window에 추가
   
4. 그리고 map.size()를 구해 answerList에 추가
   
5. 이제 window 맨 앞에 있는 값을 뺄건데,
   
6. 맨 앞에 있는 값은 바로 lt
   
7. lt의 값은 1을 줄이고,
   
8. 만약 lt의 값이 0이 되면 map에서 remove
   

🟢 Sliding Window, Hash

class Main {

    public ArrayList<Integer> solution(int n, int k, int[] intArr){
        ArrayList answerList= new ArrayList();
        HashMap<Integer, Integer> map= new HashMap<>();
        for(int i=0; i<k; i++){
            map.put(intArr[i], map.getOrDefault(intArr[i], 0)+1);
        }
        answerList.add(map.size());

        for(int i=k; i<n; i++) {
            if(map.get(intArr[i-k])>1){
                map.put(intArr[i-k], map.get(intArr[i-k]) - 1);
            }else{
                map.remove(intArr[i - k]);
            }
            map.put(intArr[i], map.getOrDefault(intArr[i], 0) + 1);
            answerList.add(map.size());
        }
        return answerList;
    }
    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[] intArr= new int[n];
        for(int i=0; i<n; i++){
            intArr[i] = sc.nextInt();
        }
        for(int x: T.solution(n, k, intArr)){
            System.out.print(x+ " ");
        }
    }
}

🔴 Two pointer, arrayList, HashMap_정답은 나오지만 time limit exceed

class Main {

    public ArrayList<Integer> solution(int n, int k, int[] intArr){
        ArrayList answerList= new ArrayList();
        HashMap<Integer, Integer> map= new HashMap<>();

        //two pointer
        int lt=0;
        int rt=lt+k;
        while(lt<n && rt<n+1){
            for(int i=lt; i<rt; i++){
                if(!map.containsKey(intArr[i])) map.put(intArr[i], 1);
            }
            answerList.add(map.size());
            map.clear();
            lt++;
            rt++;
        }


        return answerList;
    }
    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[] intArr= new int[n];
        for(int i=0; i<n; i++){
            intArr[i] = sc.nextInt();
        }
        for(int x: T.solution(n, k, intArr)){
            System.out.print(x+ " ");
        }
    }
}