[알고리즘] 4-3 매출액의 종류 - HashMap, Sliding Window 알고리즘(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 간략한 문제 설명, 예습 풀이 코드, 강의에서 설명하는 풀이 코드를 정리하고 있습니다.

강사님의 요청으로 문제를 통째로 올리지 못하는 점 양해 부탁드립니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/04-03
• 문제 설명 : n일간의 매출 기록과 연속구간의 길이 k가 주어지면 첫 번째 구간부터 각 구간별 매출액의 종류를 출력하는 문제

예습 풀이

• HashMap과 Sliding window 알고리즘을 사용하여 풀이

package inflearn.hashmap_treeset;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//매출액의 종류(hash, sliding window)
public class Main4_3 {

    public static List<Integer> solution(int n, int k, int[] arr) {
        List<Integer> answer = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();

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

        int left = 0;
        for (int right = k-1; right < n; right++) {

            map.put(arr[right], map.getOrDefault(arr[right], 0) + 1);
            answer.add(map.size());

            map.put(arr[left], map.get(arr[left]) - 1);

            if (map.get(arr[left]) == 0) {
                map.remove(arr[left]);
            }

            left++;
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {
        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());
        int[] arr = new int[n];

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

        for (int i = 0; st.hasMoreTokens(); i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        List<Integer> answer = solution(n, k, arr);
        for (Integer i : answer) {
            System.out.print(i + " ");
        }
    }
}

강의 수강후 복습 풀이

• 강의에서의 풀이와 예습 풀이 방법이 동일하여 생략