[프로그래머스] 할인 행사 (Java)

 

문제

프로그래머스

 

알고리즘

슬라이딩 윈도우, 해시맵

 

풀이

i를 1씩 늘려가며 i 번째 날부터 i + 9번째 날의 품목을 확인해야하므로

i + 1 번째 날부터 i + 9번째 날까지 9개의 원소는 그 다음에도 그대로 탐색된다.

 

따라서 슬라이딩 윈도우를 사용하여 i 번째 날의 품목의 개수를 1 빼고,  i + 10번째 날의 품목의 개수를 1 더하는 연산만 진행한다.

이때 품목이 String으로 저장되어있기 때문에 해시맵을 이용해 품목의 수를 올리고 내린다.

 

 

코드

import java.util.*;

class Solution {
	public int solution(String[] want, int[] number, String[] discount) {
		int answer = 0;

		Map<String, Integer> map = new HashMap<>();
		for (String w : want)
			map.put(w, 0);

		int left = 0;
		int right = 9;

		for (int i = 0; i <= 9; i++) {
			if (map.containsKey(discount[i]))
				map.put(discount[i], map.get(discount[i]) + 1);
		}
		if (check(map, want, number))
			answer++;

		while (right < discount.length - 1) {
			if (map.containsKey(discount[left]))
				map.put(discount[left], map.get(discount[left]) - 1);
			left++;
            
			right++;
			if (map.containsKey(discount[right]))
				map.put(discount[right], map.get(discount[right]) + 1);

			if (check(map, want, number))
				answer++;
		}
		return answer;
	}

	public boolean check(Map<String, Integer> map, String[] want, int[] number) {
		for (int i = 0; i < want.length; i++) {
			if (map.get(want[i]) != number[i]) {
				return false;
			}
		}
		return true;
	}
}