43. 매출액의 종류(Hash, sliding wind

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

 

 

풀이

package org.example;

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

public class Main43 {
    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<n; i++){
            arr[i] = sc.nextInt();
        }

        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i=0; i<k-1; i++){
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }

        int lt =0;
        for(int rt=k-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++;
        }

        for(int x : answer){
            System.out.print(x + " ");
        }
    }
}

 

풀이설명

슬라이딩 윈도우 기법을 사용해서 문제를 풀어야 시간 초과가 나지 않고 문제를 제출 할 수 있었던 문제이다.

 

초기 설정

lt

rt

20

12

20

10

23

17

10

 

현재 map 상황

key

20

12

10

value

2

1

1

 

루프 돌때마다 하는 행동 

1. lt ++  / rt ++ 

2. map 에 rt의 키값의 개수 insert 해줌

3. map 에서 lt 키값을 찾아서 -1 해줌

4. 만약 0이면 map에서 지워버림