[PS] 인프런 강의 - HashMap, HashSet, TreeSet 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

 

풀이

sliding window을 이용하여 푸는 HashMap 문제이다...!!

응용하면 되서 스스로 풀 수 있었다!

풀이는 주석으로 자세하게 적어놓았다.

 

주의할 점! lt를 당길 때 map의 key 자체를 삭제하면 안되고 값을 -1 해준다.

이렇게 하면, k일이 되서 체크할 때  value가 0이면 ! 이번에 체크할  window에는 해당 key가 없는 것이므로 삭제해주면 된다.

 

코드

1) 내가 푼 방식

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

public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();//매출 기록
		int k = in.nextInt(); //연속 매출 일수
		
		//연속 k일 동안의 매출액 종류 개수를 구간별로 구하라
		int[] arr = new int[n];
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int i=0; i<n; i++) {
			arr[i] = in.nextInt();
		}
		//k만큼 sliding window
		int lt=0;
		for(int rt=0; rt<n; rt++) { //rt 땡김
			map.put(arr[rt], map.getOrDefault(arr[rt], 0)+1); //map에 넣음
			
			if(rt-lt+1 == k) { //k일 되면 lt 땡김
				System.out.print(map.size() + " ");
                
				map.put(arr[lt], map.getOrDefault(arr[lt], 0)-1);
				if(map.get(arr[lt]) == 0) map.remove(arr[lt]); //주의!!
				lt++;
			}
		}
	}
}

2) 강사님 풀이

import java.util.*;
class Main {	
	public int solution(int n, int k, int[] arr){
		int answer, sum=0;
		for(int i=0; i<k; i++) sum+=arr[i];
		answer=sum;
		for(int i=k; i<n; i++){
			sum+=(arr[i]-arr[i-k]);
			answer=Math.max(answer, sum);
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int k=kb.nextInt();
		int[] arr=new int[n];
		for(int i=0; i<n; i++){
			arr[i]=kb.nextInt();
		}
		System.out.print(T.solution(n, k, arr));
	}
}