3. 매출액의 종류

 

import java.util.*;

class Main {

	public ArrayList<Integer> solution(int K, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<Integer>();
		Set<Integer> set = new HashSet<Integer>();
		for (int i = 0; i < arr.length - K + 1; i++) {
			for (int j = i; j < i + K; j++) {
				set.add(arr[j]);
			}
			answer.add(set.size());
			set.clear();
		}

		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(K, arr)) {
			System.out.print(x + " ");
		}
		kb.close();
	}

}

 

import java.util.*;

class Main {

	public ArrayList<Integer> solution(int K, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<Integer>();
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < K; i++) {
			if (map.containsKey(arr[i])) {
				Integer val = map.get(arr[i]) + 1;
				map.replace(arr[i], val);
			} else {
				map.put(arr[i], 1);
			}
		}

		int num = 0;
		for (int val : map.values()) {
			if (val != 0)
				num++;
		}
		answer.add(num);

		for (int i = 0; i < arr.length - K; i++) {

			map.replace(arr[i], map.get(arr[i]), map.get(arr[i]) - 1);
			if (map.containsKey(arr[i + K])) {
				Integer val = map.get(arr[i + K]) + 1;
				map.replace(arr[i + K], val);
			} else {
				map.put(arr[i + K], 1);
			}
			num = 0;
			for (int val : map.values()) {
				if (val != 0)
					num++;
			}
			answer.add(num);

		}

		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(K, arr)) {
			System.out.print(x + " ");
		}
		kb.close();
	}

}

이전에 작성한 코드가 답은 맞는데 테스트케이스 4,5가 시간초과되어서 다시 작성한 코드. 하지만 이것도 테스트케이스 5에서 시간초과가 되었다.

 

 

import java.util.*;

class Main {

	public ArrayList<Integer> solution(int K, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<Integer>();
		Set<Integer> set = new HashSet<Integer>();
		for (int i = 0; i < K; i++) {
			set.add(arr[i]);
		}
		answer.add(set.size());
		for (int i = 0; i < arr.length - K; i++) {
			boolean check = false;
			for (int j = i + 1; j < i + K + 1; j++) {
				if (arr[i] == arr[j]) {
					check = true;
					break;
				}
			}
			if (!check) {
				set.remove(arr[i]);
			}
			set.add(arr[i + K]);
			answer.add(set.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(K, arr)) {
			System.out.print(x + " ");
		}
		kb.close();
	}
}

테스트 케이스를 통과한 코드

 

 

import java.util.*;

class Main {
	public ArrayList<Integer> solution(int K, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<Integer>();
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < K; i++) {
			map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
		}
		for (int i = 0; i < arr.length - K; i++) {
			answer.add(map.size());
			map.put(arr[i], map.getOrDefault(arr[i], 0) - 1);
			map.remove(arr[i], 0);
			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(K, arr)) {
			System.out.print(x + " ");
		}
		kb.close();
	}
}

HashMap과 sliding window를 사용한 코드