[HashMap, Sliding window] 매출액의 종류 .java

설명

현수의 아빠는 제과점을 운영합니다.

현수아빠는 현수에게 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이하의 음이 아닌 정수입니다.

출력

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

예시 입력 1 

7 4
20 12 20 10 23 17 10

예시 출력 1

3 4 4 3

 

 

내 풀이

1. 매출 기록을 cost 배열에 저장

2. map을 만들어 맨 처음 k구간의 매출을 해시맵에 저장

3. 정답 리스트를 만들어 맨 처음 k 구간의 매출액 종류를 저장

4. 다음 k구간은 인덱스가 k일때부터 n까지 돌면서 이전의 맨 처음 매출을 해시맵에서 제거 -> 인덱스: i-k

 

=> 여기서 구간의 첫번째 매출을 지울 때 구현을 잘못해서 이상한 답이 나왔다

=> 무작정 제거하면 안되고 키의 값이 2개 이상이면 제거가 아니라 나온 횟수를 감소시켜야 한다

 

매출이 k구간에서 여러 번 나올 수 있는데 이 부분을 고려하지 못했다

 

5. 현재 i인 매출을 해시맵에 추가하고 이때의 map의 키 종류를 구하는 size()를 이용하여 매출액 종류를 구하여 정답 리스트에 넣는다

 

 

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

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k  = sc.nextInt();

        int[] cost = new int[n];//매출 기록

        for(int i = 0; i < n; i++){//저장
            cost[i] = sc.nextInt();
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < k; i++){//맨 처음 구간
            map.put(cost[i], map.getOrDefault(cost[i], 0) + 1);
        }
        //정답 리스트
        ArrayList<Integer> answer = new ArrayList<>();
        answer.add(map.size());

        for(int i = k; i < n; i++){
            if(map.get(cost[i-k]) == 1){//마지막 값이면
                map.remove(cost[i-k]);
            } else map.put(cost[i-k], map.get(cost[i-k]) - 1);

            map.put(cost[i], map.getOrDefault(cost[i], 0) + 1);
            answer.add(map.size());

        }

        for(int i : answer){
            System.out.print(i+ " ");
        }



    }
}

 

 

다른 풀이

내 풀이와 다른 점

- 처음 구간을 0~k-1로 설정하여 해시맵에 저장

- for문을 k-1부터 시작하여 먼저 해시맵에 put  -> size() -> 현재 구간의 가장 앞의 매출 제거

- 제거할 때, 먼저 하나 감소 -> 값이 0이면 아예 해시맵에서 제거

 

즉, 풀이의 순서만 다르다~!

 

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

public class Main {
    public ArrayList<Integer> solution(int n, int k, int[] cost){
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i = 0 ; i < k-1; i++){
            map.put(cost[i], map.getOrDefault(cost[i], 0) + 1);
        }
        int lt =0;
        for(int rt = k-1; rt < n; rt++){
            //먼저 현재 값을 넣기
            map.put(cost[rt], map.getOrDefault(cost[rt], 0) + 1);
            //k개이기 때문에 구간의 종류 저장
            answer.add(map.size());
            //현재 구간의 처음 매출 하나 감소
            map.put(cost[lt], map.getOrDefault(cost[lt], 0) - 1);
            //감소한 값이 0이면 해시맵에서 삭제
            if(map.get(cost[lt]) == 0){
                map.remove(cost[lt]);
            }
            //lt를 증가 -> 구간의 시작 하나 증가
            lt++;
        }

        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k  = sc.nextInt();

        int[] cost = new int[n];

        for(int i = 0; i < n; i++){
            cost[i] = sc.nextInt();
        }

        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i : T.solution(n,k,cost)){
            System.out.print(i+ " ");
        }



    }
}

 

💡💡

슬라이딩 윈도우는 순서를 다양하게 구현할 수 있음을 다시 알게 된 문제였다