3.売上高の種類(ハッシュ、スライドウィンドウ)

24568 ワード

(O)


賢洙のお父さんはお菓子屋を経営しています.賢秀パパは賢秀にN日間の売り上げ記録を与え、K日間連続の売り上げ種類.
区間別に購入させていただきます.
N=7の場合、7日間の販売記録は以下の通り、このときK=4
20 12 20 10 23 17 10
各4日連続の販売種類.
最初の区間は[20,12,20,10]で、売上高の種類は20,12,10で、3です.
第2段[12,20,10,23]売上高種別は4である.
第3区間[20,10,23,17]売上高種別は4.
第4区間[10,23,17,10]売上高種別は3である.
N日間の売上記録と連続区間の長さがKの場合、1区間目から区間毎に
収入の種類を出力するプログラムを作成してください.
🎁入力条件
1行目はN(5<=N<=10000)とK(2<=K<=N)である.
2行目にはN個の数字列があります.各数値は500未満の負ではなく整数です.
🎊しゅつりょくじょうけん
最初の行では、各セクションの収益カテゴリを順番に出力します.
🎁入力例
7 4
20 12 20 10 23 17 10
🎊出力例
3 4 4 3

ポリシー


ダブルポインタ+スライドウィンドウ
ダブルポインタを参照
gt増加
常にrtが増加した後に追加

答案用紙

import java.util.*;
class Main {
    public ArrayList<Integer> solution(int n, int k, int[] arr){
        ArrayList<Integer> answer = new ArrayList<>();


        // 특정 윈도우
        HashMap<Integer, Integer> map = new HashMap<>();

        // 최초 윈도우 초기화
        for(int i=0; i<k; i++){
            map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
        }
        answer.add(map.size());

        // 윈도우 옮기기
        for(int i=k; i<n; i++){
            // 기존 윈도우에 원소 추가
            map.put(arr[i], map.getOrDefault(arr[i], 0)+1);

            // 기존 윈도우의 첫 원소 삭제
            if(map.get(arr[i-k])==1){
                map.remove(arr[i-k]);
            }else{
                map.put(arr[i-k], map.getOrDefault(arr[i-k], 0)-1);
            }

            answer.add(map.size());
        }

        return answer;
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        int k=kb.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = kb.nextInt();
        }

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

    }
}
  • 前回のレッスンのコードを参照してください
  • 正解

    package com.company;
    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<>();
    
            // k가 아니라, k-1 만큼만 미리 셋팅해둔다.
            for(int i=0; i<k-1; i++){
                HM.put(arr[i], HM.getOrDefault(arr[i], 0)+1);
            }
    
            // 투포인터 + 슬라이딩 윈도우
            int lt =0;
            // * 항상 rt 증가 한 다음에 
            for(int rt=k-1; rt<n; rt++){
                // * 더하기
                HM.put(arr[rt], HM.getOrDefault(arr[rt], 0)+1);
                answer.add(HM.size());
    
                // 해당 키값(arr[lt])은 이미 HM.put(arr[rt],~)에 의해 존재하므로 getOrDefault()를 할 필요없다.
                // ** 항상 뺀 다음에
                HM.put(arr[lt], HM.get(arr[lt])-1);
                if(HM.get(arr[lt])==0) HM.remove(arr[lt]);
                // ** lt 증가
                lt++;
            }
    
            return answer;
        }
    
        public static void main(String[] args){
            Main T = new Main();
            Scanner kb = new Scanner(System.in);
            int n=kb.nextInt();
            int k=kb.nextInt();
            int[] arr = new int[n];
            for(int i=0; i<n; i++){
                arr[i] = kb.nextInt();
            }
            for(int x : T.solution(n, k, arr)){
                System.out.print(x+" ");
            }
        }
    }
  • の答えではrtは1,ltは1増加した.
    実際、答えのようにスライドウィンドウを使うだけでいいようです.