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+" ");
}
}
}
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+" ");
}
}
}
実際、答えのようにスライドウィンドウを使うだけでいいようです.
Reference
この問題について(3.売上高の種類(ハッシュ、スライドウィンドウ)), 我々は、より多くの情報をここで見つけました https://velog.io/@jhjcoding/3.-매출액의-종류Hash-sliding-windowテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol