3. 매출액의 종류

1. 문제

현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 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가 주어지면 첫 번째 구간부터 각 구간별 매출액의 종류를 출력하는 프로그램을 작성하세요.

 

2 - 1. 나의 풀이

맨 처음에는 간단히 이중 for문으로 풀다가 시간 초과가 나서 sliding window로 풀면 되겠구나! 생각이 들었다.

 

1. lt와 rt 를 사용한다.

2. arr[rt] 를 map.put할 때 value값을 0 1 2... 횟수까지 표현해준다. (getOrDefault 사용)

3. map.put을 사용할 때 count++을 해주고 count는 구간의 길이(k)까지

4. count == k 이면 구간이 다 찼으므로 해당 구간의 map.size를 answer에 저장한다음 가장 처음에 들어온 값을 제거해야한다.

5. 제거할 때 중요한건 바로 remove를 해버리면 20 12 20 10 처럼 맨 앞의 (20, 0)만 제거해야하는데 (20, 1)도 같이 제거가 되어서 size가 3에서 2로 줄어버린다. (맨 앞의 20이 제거되면 12 20 10 이 남으므로 size는 3 이어야하니까)

6. 위 상황을 방지하기 위해서 value값을 -1 한다음, 만약 value가 0 이면 remove한다.

즉, value가 0인 key는 삭제해줘야한다!

 

 

2 - 2. 나의 코드

package HashMap_TreeSet;

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

public class HashMap_03 {
    public static int[] solution(int[] arr, int n, int k) {
        int[] answer = new int[n - k + 1];
        HashMap<Integer, Integer> map = new HashMap<>();
        int lt=0;
        int count = 0;

        for (int rt = 0; rt < n; rt++) {
            map.put(arr[rt], map.getOrDefault(arr[rt], 0)+1);
            count++;
            while (count == k) {
                answer[lt] =map.size();
                //한 번에 key값이 사라지는걸 방지
                map.put(arr[lt], map.get(arr[lt])-1);
                if(map.get(arr[lt]) == 0) map.remove(arr[lt]);
                lt++
                count--;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        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 : solution(arr, n, k)) {
            System.out.print(x + " ");
        }

    }


}

/*  이중 for문 시간초과
    private static int[] solution(int[] arr, int n, int k) {
        int[] answer = new int[n - k + 1];
        //key는 매출액 value 매출액의 개수
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n - k + 1; i++) {
            map.clear();
            int j = i+k;
            for (int cnt = i; cnt < j; cnt++) {
                map.put(arr[cnt], map.getOrDefault(arr[cnt], 0)+1);
            }
            answer[i] = map.size();
        }
        return answer;
    }*/

 

3 - 1. 강의 풀이

나와 같은 로직을 사용했지만 코드는 조금 다르다!

 

1. HashMap에 0~ k-1 번쨰 까지 넣어 놓은 다음

2.put(arr[rt])를 한다음 size를 answer에 저장한다.

3. arr[lt]를 해쉬에서 value-1 or remove 한다

2번 3번 과정을 반복한다.

 

3번 과정에서 value-1하고 value가 0이면 remove하는 아이디어가 가장 중요!

 

3 - 2. 강의 코드

package HashMap_TreeSet;

import java.util.*;

public class HashMap_03_solution {
    public static ArrayList<Integer> solution(int[] arr, int n, int k) {
        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) {
        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 : solution(arr, n, k)) {
            System.out.print(x + " ");
        }

    }
}

4. 얻어갈 점

정답률 28%여서 어려운가 했는데 시간초과 때문에 정답률이 낮은거 같다.

O(n)으로 풀어야 한다.

해쉬 테이블의 의미도 HashMap을 생각해보니 뭔가 알거같기도 하고...