섹션 4. HashMap, TreeSet - 3. 매출액의 종류

📌 문제 설명

현수의 아빠는 제과점을 운영하고 있고, N일 동안의 매출기록을 가지고 있습니다. 현수는 이 기록을 가지고 연속된 K일 동안의 매출액 종류의 개수를 구하려 합니다.

즉, 매일의 매출 데이터를 보고 연속된 K일 동안 서로 다른 매출액(숫자)의 개수를 계산하여 출력합니다.

---

📝 입력 & 출력

입력

• 첫째 줄: N(5 ≤ N ≤ 100,000), K(2 ≤ K ≤ N)
• 둘째 줄: N개의 매출기록 숫자 (각 숫자는 0 이상 500 이하)

출력

• 각 연속 K일 간의 매출액 종류의 수를 공백으로 구분하여 출력

---

🔸 예제 입력 & 출력

예제 입력 1

7 4
20 12 20 10 23 17 10

 

예제 출력 1

3 4 4 3

---

💡 해결 방법

• 슬라이딩 윈도우와 HashMap을 조합하여 효율적으로 각 구간의 매출 종류를 계산합니다.

알고리즘 순서

1. 처음 K일을 맵에 기록하고, 종류 수 저장
2. K일부터 끝까지 반복하며
   • 왼쪽 끝 요소는 count -1 (0이면 삭제)
   • 오른쪽 새 요소는 count +1 (or 새로 추가)
3. 각 단계마다 map.size()를 결과에 저장

• HashMap을 사용해 각 매출액이 몇 번 등장하는지 세고, 0이 되면 제거하여 정확한 종류 수 유지

---

💻 코드 구현 (Java)

package partTwoPointers;

import java.util.*;

public class Problem3 {
	public ArrayList<Integer> solution(int n, int k, int[] arr){
		ArrayList<Integer> result = 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);
		}
		result.add(map.size());

		// 슬라이딩 윈도우 이동
		for(int i=k; i<n; i++) {
			// 왼쪽 값 제거
			map.put(arr[i-k], map.get(arr[i-k]) - 1);
			if(map.get(arr[i-k]) == 0) map.remove(arr[i-k]);

			// 오른쪽 새 값 추가
			map.put(arr[i], map.getOrDefault(arr[i], 0)+1);

			result.add(map.size());
		}
		return result;
	}

	public static void main(String[] args) {
		Problem3 T = new Problem3();
		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 + " ");
		}
		kb.close();
	}
}

---

📖 코드 설명

• map.getOrDefault(key, 0) : key가 없으면 0으로 시작
• map.size() : 현재 윈도우 내 서로 다른 매출액 종류 수
• map.remove(key) : 등장 횟수가 0이 되면 map에서 완전히 제거 (정확한 종류 수 계산)

---

⏳ 시간 복잡도 분석

• 각 원소는 한 번씩 윈도우에 들어가고 한 번씩 나감 → O(N)
• HashMap의 삽입/삭제/조회는 O(1) 평균
• 총 시간 복잡도: O(N) 

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런