[코테4_3] 최대매출 구하기

✔ 내답-> 정답이긴 하나 타임초과

import java.util.*;

public class Main{
  public static int[] solution(int n, int k, int[] arr){
    int[] answer = new int[n-k+1];
    for(int i=0;i<=n-k;i++){
     HashMap<Integer, Integer> map = new HashMap<>();
      for(int j=i;j<=i+k-1;j++){
          map.put(arr[j],map.getOrDefault(arr[j],0)+1);
       }
      //Set set = map.entrySet();
      //System.out.println(set);
      answer[i]=map.size();
    }
   return answer;
  }
  public static void main(String[] args){
    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 : solution(n,k,arr)){
    System.out.print(x+" ");
    }
  }

}

✔강의 듣고 힌트 얻은 후에 해도 시간 초과

import java.util.*;

public class Main{
  public static int[] solution(int n, int k, int[] arr){
    int lt=0, rt=k-1;
    int[] answer = new int[n-k+1];
    while(rt<=n-1){
    HashMap <Integer, Integer> map = new HashMap<>();
    for(int i=lt;i<=rt;i++){
    map.put(arr[i],map.getOrDefault(arr[i],0)+1);
    }
    answer[lt]=map.size();
    lt++;
    rt++;
    }
     return answer;
  }
  public static void main(String[] args){
    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 : solution(n,k,arr)){
    System.out.print(x+" ");
    }
  }

}

✔️ 강의 완전 다 듣고 난 후 -> 정답

import java.util.*;


public class Main {
 public static List<Integer> solution(int N, int K, int[] arr){
	List<Integer> answer = new ArrayList<>() ;	
	int lt=0;
	HashMap <Integer,Integer> map = new HashMap<>();
    for(int i=0;i<K-1;i++) {
        map.put(arr[i], map.getOrDefault(arr[i],0)+1);    	
    }
    
    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]);//key자체를 삭제
     lt++;
    }
	
	return answer;
	 
 }
 public static void main(String[] args){
  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 : solution(N,K,arr)) {
	  System.out.print(x+" ");
  }
  
 }
}

할 때마다 새롭게 HashMap을 만드는게 아니라
옮겨 다니면서 추가되는 것과 삭제되는 것만 추가 삭제를 해서
최소한의 이동만 했다.