[Inflearn] 자바 알고리즘 문제풀이 #04-03 3. 매출액의 종류(Hash, 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이하의 음이 아닌 정수입니다.

 

출력 

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

 

 

 

내 풀이 = 선생님 풀이

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

public class Main4_3 {
    public ArrayList<Integer> Solution(int n, int k, int[] arr) {
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> HM = new HashMap<>();
        for (int i = 0; i < k-1; i++) {
            HM.put(arr[i], HM.getOrDefault(arr[i], 0)+1);
        }
        int lt=0;
        for (int rt = k-1; rt < n; rt++) {
            HM.put(arr[rt], HM.getOrDefault(arr[rt], 0)+1);
            answer.add(HM.size());
            HM.put(arr[lt], HM.get(arr[lt])-1);
            if(HM.get(arr[lt])==0) HM.remove(arr[lt]);
            lt++;
        }
        return answer;
    }

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

15~17 행이 정답의 핵심인데, 그것을 생각해내고 풀어서 굉장히 뿌듯했던 문제다.

슬라이딩 윈도우에서는 3-3 최대매출 문제와, 지금 4-3 매출액의 종류 문제처럼 k 값을 이용해 비교할 값들을 먼저 더하고, lt와 rt  값으로 미끄러지면서 특정 행동을 반복하는 방법이 있다는 것을 알고 있으면 좋을 것 같다.

https://rookie-programmer.tistory.com/55

[Inflearn] 자바 알고리즘 문제풀이 #03-03 3. 최대 매출

 

 

 

결과