[알고리즘]HashMap & Sliding window - 매출액의 종류

3. 매출액의 종류
N일간의 매출기록과 연속구간의 길이 K가 주어지면 첫 번째 구간부터 각 구간별 매출액의 종류를 출력하는 프로그램

입력) 첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다.
출력) 첫 줄에 각 구간의 매출액 종류를 순서대로 출력합니다.

 

 

1)

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

public class Main {
	
	public static 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-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++;
		}
		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int[] arr = new int[n];
		for (int i=0; i<n; i++) {
			arr[i] = scanner.nextInt();
		}
		for (int x : solution(n, k, arr)) {
			System.out.print(x + " ");
		}
	}

}

 

2)

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

public class Main {
	
	public static 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 rt=k; rt<n; rt++) {
			map.put(arr[rt], map.getOrDefault(arr[rt], 0)+1); // rt -> 키로 추가
			map.put(arr[rt-k], map.get(arr[rt-k])-1); // lt(rt-k) 키값-1
			if (map.get(arr[rt-k])==0) map.remove(arr[rt-k]);			
			answer.add(map.size());
		}
		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int[] arr = new int[n];
		for (int i=0; i<n; i++) {
			arr[i] = scanner.nextInt();
		}
		for (int x : solution(n, k, arr)) {
			System.out.print(x + " ");
		}
	}

}

---

결과

입력
7 4
20 12 20 10 23 17 10

출력
3 4 4 3