JAVA 알고리즘 문제 - 매출액의 종류(sliding window)

매출액의 종류(sliding window)

 

설명

현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 매출액의 종류를

각 구간별로 구하라고 했습니다.

만약 N=7이고 7일 간의 매출기록이 아래와 같고, 이때 K=4이면

20 12 20 10 23 17 10

각 연속 4일간의 구간의 매출종류는

첫 번째 구간은 [20, 12, 20, 10]는 매출액의 종류가 20, 12, 10으로 3이다.

두 번째 구간은 [12, 20, 10, 23]는 매출액의 종류가 4이다.

세 번째 구간은 [20, 10, 23, 17]는 매출액의 종류가 4이다.

네 번째 구간은 [10, 23, 17, 10]는 매출액의 종류가 3이다.

N일간의 매출기록과 연속구간의 길이 K가 주어지면 첫 번째 구간부터 각 구간별

매출액의 종류를 출력하는 프로그램을 작성하세요.

 

입력

첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.

두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

 

출력

첫 줄에 각 구간의 매출액 종류를 순서대로 출력합니다.

 

입력예시

7 4
20 12 20 10 23 17 10

 

출력예시

3 4 4 3

 

전체코드

package Level1;

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

public class Main {
	
	public ArrayList<Integer> test(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){
		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.test(n, k, arr)) System.out.print(x+" ");
    }
}

---

여기서는 sliding window방식을 사용하여 문제를 해결하려고한다.

		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);
		}

결과값을 담을 ArrayList, 같은 연속된 k번째에서 중복값 체크를 위한 map을 만들어주었고

여기서 입력 값으로 우리는 n : 7, k: 4 , arr : [ 20 12 20 10 23 17 10 ]로 입력을 받았다. 

Key	Value
20	2
12	1

위 코드를 수행 결과 map에 이와같은 형태의 데이터가 들어간다.

 

일정한 범위(k=4)를 유지하며 이동하기 위해 lt와 rt를 사용하려고한다.

		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;

 

1. rt = 3, lt = 0

Key	Value
20	2
12	1
10	1

map.size() = 3 

answer.add(3) 추가

 

map.put(arr[lt], map.get(arr[lt])-1);에 의해 Key = 20 , Value = 1로 변경

Key	Value
20	1
12	1
10	1

(map.get(arr[lt])==0) 조건 False 

lt++ 증가

 

---

2. rt = 4, lt = 1

Key	Value
20	1
12	1
10	1
23	1

map.size() = 4

answer.add(4) 추가

 

map.put(arr[lt], map.get(arr[lt])-1);에 의해 Key = 12 , Value = 0로 변경

Key	Value
20	1
12	0
10	1
23	1

 

(map.get(arr[lt])==0) 조건 True 해당 Key,Value삭제

Key	Value
20	1
10	1
23	1

 

lt++ 증가

---

3. rt = 5 lt = 2

Key	Value
20	1
10	1
23	1
17	1

map.size() = 4

answer.add(4) 추가

 

 

map.put(arr[lt], map.get(arr[lt])-1);에 의해 Key = 20 , Value = 0로 변경

Key	Value
20	0
10	1
23	1
17	1

(map.get(arr[lt])==0) 조건 True 해당 Key,Value삭제

Key	Value
10	1
23	1
17	1

lt++ 증가

---

4. rt = 6 lt = 3

Key	Value
10	2
23	1
17	1

map.size() = 3

answer.add(3) 추가

 

 

 

최종 answer의 결과값 3 4 4 3