매출액의 종류(해쉬,투포인터)

만약 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이다.

이때 매출액의 종류의 갯수를 구하는 문제

 

풀이 방법 - 구간값이 4라고 가정하면 앞 3일의 값의 종류를 map으로 받아서 키 - 매출, 값 - 그 매출이 나온 횟수를 받는다

4일부터는 그날의 값을 map에 getoradd+1로 더하고 map의 size로 매출액의 종류를 구하고

맨 앞의 매출액을 get -1 로 뺀후 그 값이 0이면 나온 횟수가 0이므로 제거한다

 

먼저 풀어볼때는 투포인터를 사용하지 않고 구간이 고정되어 있으니 4일이면 0,1,2 일을 미리 구해두고 뒤에 날짜를 추가하면서 한칸씩 전진하는 것으로 풀어보았다

 

한칸씩 전진할 때는 맨 앞 날짜의 요소 갯수를 하나 빼고 그게 0이면 아예 값이 없으니 해당하는 키값을 제거하고

map의 size를 출력하면 종류가 나온다

import java.util.*;
public class Main {

    public void Solution(int n, int k, int[] arr){
        HashMap<Integer, Integer> map = new HashMap<>();
        int lt =0, rt =0;
        for(int i =0; i < k-1; i++){
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
        }

        for(int i = k-1; i < n; i++){
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
            System.out.print(map.size() + " ");
            map.put(arr[i-k+1],map.get(arr[i-k+1])-1);
            if(map.get(arr[i-k+1]) == 0) map.remove(arr[i-k+1]);
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) arr[i] = in.nextInt();

        T.Solution(n,k,arr);
    }
}

 

강의를 듣고 투포인터를 사용한 풀이

기존에 i-k+1으로 구하던 걸 lt로 대체하고 루프 마지막에 lt++ 하는 방법으로 바꾸었다

출력도 arraylist를 사용해서 solution이 아니라 main 함수에서 출력하는 걸로 변경

 

import java.util.*;
public class Main {

    public ArrayList<Integer> Solution(int n, int k, int[] arr){
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer> answer = new ArrayList<>();
        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++; // lt 전진
        }

        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) arr[i] = in.nextInt();

        for (int x : T.Solution(n,k,arr)) System.out.print(x + " ");
    }
}