[해쉬맵+슬라이딩윈도우] 매출액의 종류 (인프런 알고리즘 4-3)

문제 풀이 (JAVA)

import java.io.*;
import java.util.*;
public class part4_3 {

	public static void main(String[] args) throws IOException{
		// 매출액의 종류
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st= new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		String str = br.readLine();
		String [] a = str.split(" ");
		List<Integer> answer = solution(a,N,K);
		for(Integer s : answer) {
			bw.write(s+" ");
		}
		bw.flush();
		bw.close();
	}
	private static List<Integer> solution(String [] a, int N, int K) {

		HashMap<String,Integer> map = new HashMap<>();
		List<Integer> list =new ArrayList<>();
		int lt=0, rt=0;
		int cnt=0;
		while(lt < N  && rt < N) {			
			// 오른쪽 포인터 rt와 왼쪽 포인터 lt의 차가 K보다 작다면 윈도우가 다 안찼으므로
			if((rt-lt) < K) {
				// map에 추가한다. key가 존재할시 기존 값에 +1을 한다.
			   map.put(a[rt], map.getOrDefault(a[rt], 0)+1);
			   rt++; // 오른쪽 슬라이드 포인터 증가
			// K의 길이와 포인터의 차가 같다면 윈도우의 사이즈가 K인것이므로
			}else if((rt-lt) == K){
				list.add(map.size()); // 해당 윈도우의 맵 사이즈가 숫자의 종류이므로 리스트 추가
				map.put(a[lt], map.getOrDefault(a[lt], 0)-1); // 맨 왼쪽 슬라이드 값 -1
				if(map.get(a[lt]) == 0) { // 해당 값이 0이 된다면 중복되는 맵이 없으므로
					map.remove(a[lt]); // 해당 숫자 맵에서 제거
				}
				// 오른쪽 포인터가 마지막을 왔을때 증가된 포인터 처리
				if(rt==N-1) {
					// 해당 값을 맵에 추가하여 리스트에 더하고 종료한다.
					map.put(a[rt], map.getOrDefault(a[rt],0)+1);
					list.add(map.size());
					break;
				}
				lt++; // 왼쪽 슬라이드 포인터 증가 
			}

		}		
		return list;
	}
}

해시 함수 정리

map.put(key,value) : map에 해당되는 key에 value를 INSERT or UPDATE 한다.

map.get(key) : key에 해당하는 value를 리턴한다.

map.containsKey(key) : map에 key가 존재하는지 확인하여 존재하면 true, 존재하지 않을 경우 false를 리턴한다.

map.getOrDefault(key,0) : map에 key가 존재하면 key의 value를 리턴하고, key가 존재하지 않으면 0을 리턴한다.

map.size() : map의 사이즈를 리턴한다.

map.remove(key) : key의 value를 출력하고, 해당 되는 key를  map에서 제거한다.

for (Character key : map.keySet()) : key를 순서대로 탐색한다.

 

 

주요 핵심 포인트

1.  해당 문제는 슬라이딩윈도우와 해쉬맵을 사용하여 풀어보는 응용 문제이다.

2. K의 길이와 lt , rt의 포인터 인덱스 번호의 차를 이용하여 길이가 rt와 lt를 증가시키면서 풀었다.

3. K개의 길이만큼 도달했을시 getOrDefault 함수를 사용하여 기존값에 -1을 하여 0이 된다면 중복값이 없으므로 해당 값을 remove하고, 1이라면 중복값이므로 해쉬맵에서 제거하지 않고 두었다. 결과적으로 중복값은 남되 새로운 값은 추가할수 있게 된다.

4. 마지막 rt의 인덱스를 쓰고 증가시켰을때 마지막 윈도우를 처리하기 위하여 break 문을 추가하였다.