[인프런] 04_03 매출액의 종류

📖  문제

---

• 첫 줄에 N과 K 입력
• 두 번째 줄에 N개의 숫자열이 주어진다.
  • N일 동안의 매출 기록을 주고 연속된 K열 동안의 매출액의 종류를 각 구간별로 구하시오.
  • N이 7이고 7일간의 매출 기록이 아래와 같으며, K는 4이면 아래와 같다.

N=7, K=4

 

⚠️  주의사항

---

• Sliding Window 방식과 HashMap을 같이 이용하면 될 것 같습니다.
• 이동하면서 맨 왼쪽칸만 빼던 것과는 다르게 해야 합니다.
  • 매출액이 7일동안 [20 12 20 10 23 17 10]이고 4일간의 매출액의 종류를 구해보겠습니다.
  • 첫 구간 [20 12 20 10] -> 3개
  • 두 번째 [12 20 10 23] -> 4개 
  • 세 번째 [20 10 23 17] -> 3개 
• 위에 보이는 것처럼 맨 왼쪽꺼가 사라지는 것이 아니라 종류를 세는 것이므로 다르게 생각해야 합니다.

✍️  이해

---

/**
 * 1. N(총 매출 일), K(찾고자 하는 일), arr(매출액) 입력, ArrayList<Integer> answer
 * 2. Sliding Window 사용 해서 left, right 변수 지정
 * 3. K - 1까지 map.put(arr[i] 값 추가
 *  3-1. K가 4라고 치면 arr[0], arr[1], arr[2] 값을 map에 put
 * 4. right = k - 1 -> N
 *  4-1. arr[right]를 map에 put -> arr[3] 추가
 *  4-2. answer에 map.size()를 추가
 *  4-3. K(4)칸 씩 왼쪽에서 오른쪽으로 옮겨가면서 비교하는데 옮긴후에도 1일 경우 빼줘야함
 *  4-4. map의 key값이 0인 경우 그 값은 remove 해줌
 */

 

✏️  풀이

---

여기서 두 가지 풀이를 써보겠습니다.

 

제가 직접 풀어봤던 풀이입니다. 이중 for문을 이용해서 4칸씩 이동할 때마다 4칸 안에 모두 확인하는 방법입니다.

하지만 이 방법에 경우는 엄청난 양의 데이터가 들어왔을 때 속도가 엄청 느려집니다.

결국 10만개의 값이 들어오자 Time Limit이 걸려버렸습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

    public String solution(int N, int K, int[] arr) {

        int cnt = 0;
        int num = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N - K + 1; i++) {
            HashMap<Integer,Integer> map = new HashMap<>();
            for (int j = num; j < K + num; j++) {
                map.put(arr[j], 0);
                cnt = map.size();
            }
            num++;
            sb.append(cnt).append(" ");

        }
        return sb.toString();
    }


    public static void main(String[] args) throws IOException {

        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(T.solution(N, K, arr));
    }
}

---

위에 코드가 Time Limit Exceeded 오류가 생겨서 새롭게 만들어본 코드입니다.

 

이중 for문에서 단일 for문으로 바꿨습니다.

 

그 결과 속도는 아래와 같습니다.

 

적은 양의 데이터는 Time이 비슷해보이지만 막대한 양의 데이터가 들어온 4번과 5번의 경우에는 위에 코드와 시간차이가 확연히 난다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

    public ArrayList<Integer> solution(int N, int K, int[] arr) {

        ArrayList<Integer> answer = new ArrayList<>();
        int left = 0;

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

        for (int i = 0; i < K - 1; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }

        for (int right = K - 1; right < N ; right++) {

            map.put(arr[right], map.getOrDefault(arr[right], 0)+1); // 배열의 right번째 값을 Key, value 값을 1로 추가
            answer.add(map.size()); // map의 size 값을 answer에 추가
            map.put(arr[left], map.get(arr[left])-1); // 오른쪽으로 한 칸 이동 했을 때 map에 저장 된 배열의 left칸의 값이 0인지 체크하기 위해서 value 값 변경
            if(map.get(arr[left])==0) map.remove(arr[left]); // 0인 경우 쓸모가 없으므로 remove
            left++;
        }
        return answer;
    }


    public static void main(String[] args) throws IOException {

        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i : T.solution(N, K, arr)) System.out.print(i + " ");
    }
}

---