자바 알고리즘 문제 풀이 입문. 섹션4. HashMap, TreeSet (해쉬, 정렬지원 Set) : 매출액의 종류

 

https://hyejin.tistory.com/1228

자바 알고리즘 문제 풀이 입문. 섹션4. HashMap, TreeSet (해쉬, 정렬지원 Set) : 아나그램

-> 이전 문제 풀이 

 

 

3. 매출액의 종류 

설명

현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 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

public ArrayList<Integer> solution(int n, int k, int[] arr)
{
   ArrayList<Integer> answer = new ArrayList<>();
   Map<Integer, Integer> map = new HashMap<>();
   
   for (int i = 0; i < n; i++)
   {
      if (i < k)
      {
         map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
         if (i == k - 1) {
            answer.add(map.keySet().size());
         }
      }
      else
      {
         map.put(arr[i - k], map.get(arr[i - k]) - 1);
         if (map.get(arr[i - k]) == 0)
         {
            map.remove(arr[i - k]);
         }
         map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
         answer.add(map.keySet().size());
      }
   }
   
   return answer;
}

👩‍💻 : 이번 문제는 Sliding Window로 문제를 푸는데 이때 HashMap 을 사용하는 방식이었다. 

우선 i가 k-1 까지 돌 때는 HashMap에 기본 값을 세팅해주고 이 키 값의 size를 arrayList에 담아줬다. (첫번째 구간의 매출 종류) 

그 다음 i - k 번째 값은 첫번째 구간에서 벗어나기 때문에 HashMap에서 그 값을 빼주고, 이때 HashMap에서 arr[i-k]의 value 값을 뺐더니 0 이 되었을 경우에는 key값을 제거해줘야 한다. (안그러면 size 값 계산할 때 value가 0 인 키값도 포함되기 때문!) 

그 다음 한 칸 옆으로 가야하기 때문에 map에 arr[i]  키 값을 +1 해주고, 그 다음 answer에 size를 add해줬다. 

 

 

문제 풀이 2

public ArrayList<Integer> solution2(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;
}

👾 : 강사님도 나와 비슷하게 풀었는데 강사님은 우선 k-1 개만 map에 세팅해주고 lt, rt 값을 이용해서 값을 더하고 계산하고 하는 방식으로 풀어나갔다. 

먼저 반복문을 통해서 HashMap에 k-1 만큼 값을 우선 세팅해주고, 

그 다음 반복문에서는 rt가 k-1부터 시작해서 옆으로 이동하도록 했다. 그래서 map에 arr[rt] 키 값을 구했을 때 없으면 0, 아니면 그 값을 가져와 + 1 해주고, HashMap의 사이즈를 answer에 add 해줬다. 

 

그러고 다음 lt 값을 움직여서 HashMap에서 lt 키 값에 대한 값을 -1  해주는데 이때 HashMap의 값이 0이되면 HashMap에서 remove 해줬다. (그래야 HashMap 사이즈 계산할 때 포함 안함 !!) 

그 다음 lt 값을 +1 증가해주면 값을 구할 수 있다.