매출액의 종류

설명

현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 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

 

소스 코드 1

import java.util.HashMap;
import java.util.Scanner;

//매출액의 종류
public class Main {
    public static int[] solution(int N, int K, int[] arr) {
        int[] ans = new int[N - K + 1];
        int lt = 0; //left 인덱스 변수
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < K; i++) { //0~K-1 인덱스 까지 초기화
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1); //
        }

        for (int rt = K; rt < N; rt++) {//lt rt 하나씩 늘리며 구간을 정해 한칸씩 오른쪽으로 옮기는 루프
            ans[lt] = map.size(); //map의 크기 = 매출액 종류의 개수
            if (map.get(arr[lt]) >= 2) { //맨 왼쪽 인덱스 값이 map에 2개 이상이라면 하나만 줄인다
                map.put(arr[lt], map.get(arr[lt]) - 1);
            } else { // 만약 1개거나 없다면 그냥 삭제
                map.remove(arr[lt]);
            }
            lt++;
            //arr배열의 인덱스 rt의 값이 있다면 거기에 +1 없다면 0에 +1
            map.put(arr[rt], map.getOrDefault(arr[rt], 0) + 1);
        }
        ans[lt] = map.size(); //마지막 ans배열 대입 안해줬으므로 여기서 해줘야 함

        return ans;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }

        for (int s : solution(N, K, arr)) {
            System.out.print(s + " ");
        }
    }
}