[Java] 매출액의 종류

Problem 💻

현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 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가 주어지면 첫 번째 구간부터 각 구간별

매출액의 종류를 출력하는 프로그램을 작성하세요.

 

Solution 💡

1. 슬라이딩 윈도우 + HashMap 사용

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

public class INF0403 {
    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();
        }

        INF0403 main = new INF0403();
        for (int i : main.solution(n, k, arr)) {
            System.out.print(i + " ");
        }
    }

    /**
     * 매출액의 종류를 구하는 함수
     *
     * @param N     전체 날짜 수
     * @param K     연속 구간 길이
     * @param sales 매출 기록 배열
     * @return 각 구간별 매출액 종류를 담은 리스트
     */
    public List<Integer> solution(int n, int k, int[] sales) {
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();

        // 첫 번째 윈도우 초기화
        for (int i = 0; i < k - 1; i++) {
            map.put(sales[i], map.getOrDefault(sales[i], 0) + 1);
        }

        // 슬라이딩 윈도우 시작
        int lt = 0; // 왼쪽 포인터
        for (int rt = k - 1; rt < n; rt++) {
            // 윈도우에 새롭게 포함될 값 추가
            map.put(sales[rt], map.getOrDefault(sales[rt], 0) + 1);
            // 현재 윈도우에 포함된 고유 매출 값의 개수를 결과에 추가
            answer.add(map.size());
            // 윈도우에서 빠져나가는 값의 빈도를 감소
            map.put(sales[lt], map.get(sales[lt]) - 1);
            // 만약 빈도가 0이 되면, 맵에서 해당 키 제거
            if (map.get(sales[lt]) == 0) {
                map.remove(sales[lt]);
            }
            // 윈도우 왼쪽 포인터를 한 칸 이동
            lt++;
        }

        return answer;
    }
}

전제

• n: 총 날짜 수.
• k: 연속 구간 길이.
• sales: 매출 데이터 배열.

풀이

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

• 첫 번째 윈도우 초기화
  • k-1번째까지 미리 map에 넣어놓는 초기값 세팅

int lt = 0; // 왼쪽 포인터
for (int rt = k - 1; rt < n; rt++) {
    map.put(sales[rt], map.getOrDefault(sales[rt], 0) + 1);
    answer.add(map.size());
    map.put(sales[lt], map.get(sales[lt]) - 1);
    if (map.get(sales[lt]) == 0) {
        map.remove(sales[lt]);
    }
    // 윈도우 왼쪽 포인터를 한 칸 이동
    lt++;
}

• 슬라이딩 윈도우 반복
  1. 배열의 k번째 수를 넣는다 인덱스로는 arr[k-1]
  2. 연속 구간 길이 k를 만족했으므로 현재까지의 종류를 map에 넣는다.
  3. 윈도우에서 빠져나가는 값을 -1 한다.
  4. 만약 이 값이 0이 됐다면 map에서 제거한다 ← 중요!
  5. 윈도우 왼쪽 포인터를 한 칸 이동한다. (다음에 제거할 대상을 위해)