[문제풀이] 04-03. 매출액의 종류

인프런, 자바(Java) 알고리즘 문제풀이

HashMap, TreeSet(자료구조) - 0403. 매출액의 종류

🗒️ 문제

🎈 나의 풀이

	private static String solution(int n, int m, int[] arr) {
        StringBuilder answer = new StringBuilder();
        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i=0; i<m; i++) {
            map.merge(arr[i], 1, Integer :: sum);
        }

        answer.append(map.size()).append(" ");

        for(int i=m; i<n; i++) {
            map.merge(arr[i-m], -1, Integer :: sum);
            if(map.get(arr[i-m]) < 1) map.remove(arr[i-m]);

            map.merge(arr[i], 1, Integer :: sum);
            answer.append(map.size()).append(" ");
        }

        return answer.toString();
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];

        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println(solution(n, m, arr));
    }

🖍️ 강의 풀이

    public ArrayList<Integer> solution(int n, int k, int[] arr){
		ArrayList<Integer> answer = new ArrayList<>();
		HashMap<Integer, Integer> HM = new HashMap<>();
		for(int i=0; i<k-1; i++){
			HM.put(arr[i], HM.getOrDefault(arr[i], 0)+1);
		}
		int lt=0;
		for(int rt=k-1; rt<n; rt++){
			HM.put(arr[rt], HM.getOrDefault(arr[rt], 0)+1);
			answer.add(HM.size());
			HM.put(arr[lt], HM.get(arr[lt])-1);
            		if(HM.get(arr[lt])==0) HM.remove(arr[lt]);
            		lt++;
		}
		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();
		}
		for(int x : T.solution(n, k, arr)) System.out.print(x+" ");
	}

💬 짚어가기

해당 문제는 sliding window와 Map을 이용하여 해결할 수 있다.
Map에 최초 k일 동안의 발생한 매출액을 key, 해당 매출액 발생 빈도를 value로 보관한다.
그 다음 날부터 매출액을 순회하며 중복되지 않는 매출액의 종류를 카운트한다.

☕️ 여담으로

처음 구현 시에 지금과 동일한 로직에서 시간 초과가 발생했다. 원인은 answer을 담는 자료형.
습관 처럼 String 자료형으로 만들었더니 반복문을 돌며 매번 새로운 객체를 생성하고,
이 것이 실행 시간을 더욱 오래 걸리게 하였다. 상황에 맞게 StringBuilder 를 애용하자...