[해쉬맵 슬라이딩] 3. 매출액의 종류

3. 매출액의 종류

 

설명

현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 매출액의 종류를

각 구간별로 구하라고 했습니다.

만약 N=7이고 7일 간의 매출기록이 아래와 같고, 이때 K=4이면

20 12 20 10 23 17 10

각 연속 4일간의 구간의 매출종류는

첫 번째 구간은 [20, 12, 20, 10]는 매출액의 종류가 20, 12, 10으로 3이다.

두 번째 구간은 [12, 20, 10, 23]는 매출액의 종류가 4이다.

세 번째 구간은 [20, 10, 23, 17]는 매출액의 종류가 4이다.

네 번째 구간은 [10, 23, 17, 10]는 매출액의 종류가 3이다.

N일간의 매출기록과 연속구간의 길이 K가 주어지면 첫 번째 구간부터 각 구간별

매출액의 종류를 출력하는 프로그램을 작성하세요.

입력

첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.

두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

출력

첫 줄에 각 구간의 매출액 종류를 순서대로 출력합니다.

예시 입력 1 

7 4
20 12 20 10 23 17 10

예시 출력 1

3 4 4 3

 

 

<<풀이>>

 

-나의 풀이- 

 

일단 나의 풀이는 세가지 였는데 한 가지는 순서만 다른 거라 하나만 넣었다 ㅋㅋ 

 

우선, 정답은 맞지만 시간초과로 인해 오답으로 처리 되었다 ㅠㅠ

 

이쯤 되면 while과 for문을 동시에 썼을 때 시간복잡도를 잘 이해해야 하겠다!!

 

그리고 해쉬의 clear()메서드를 활용했다.

import java.util.*;

class Main {

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

        for(int lt = 0; lt < n - m + 1; lt++) {
            for(int rt = lt; rt < m + lt; rt++) {
                map.put(arr[rt], 1);
            }

            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 + " ");
        }

    }
}

 

 

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)

 

역시 강사님은 깔끔하게 푸셨다. ㅋㅋㅋㅋ

 

일단, 슬라이딩으로 구현했고, 이를 활용할 때는 미리 셋팅 한다는 것을 생각하면 좋을 것 같다.

 

그리고 슬라이딩을 활용할 수 있다는 것이다. 만약 기본 셋팅이 없으면 for구문을 활용할 수 밖에 없는 것이다.

 

이를 고려하면 쉽게 슬라이딩의 활용을 이해할 수 있다.

import java.util.*;

class Main {

    private ArrayList<Integer> solution(int n, int m, int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer> answer = new ArrayList<>();
        for(int i = 0; i < m - 1; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }
        int lt = 0;
        for(int rt = m - 1; rt < n; rt++) {
            map.put(arr[rt], map.getOrDefault(arr[rt], 0) + 1);
            answer.add(map.size());
            map.put(arr[lt], map.get(arr[lt]) - 1);
            if(map.get(arr[lt]) == 0) map.remove(arr[lt]);
            lt++;
        }
        
        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 + " ");
        }

    }
}

 

오늘도 좀 더 배워간돠 ~~