먼저 정현이가 원하는 제품과 수량을 하나의 맵(딕셔너리)으로 정리합니다. 예를 들어, 정현이가 바나나 3개, 사과 2개, 쌀 2개, 돼지고기 2개, 냄비 1개를 원한다면 이를 {바나나: 3, 사과: 2, 쌀: 2, 돼지고기: 2, 냄비: 1}과 같이 표현할 수 있다. XYZ 마트는 매일 한 가지 제품을 할인하는데, 회원 가입 후 10일 동안 매일 할인 제품을 구매할 수 있으므로, 정현이가 원하는 제품을 모두 할인받으려면 10일간의 할인 제품 목록이 위의 맵과 정확히 일치해야 한다. 할인 제품의 총 개수도 10개여야 하기 때문에, 10일간의 구간에서 각 제품의 등장 횟수를 세어 목표 맵과 일치하는지 확인하면 된다.
이를 위해 할인 제품 배열(discount 배열)에서 연속된 10일 구간을 하나씩 살펴본다. 처음에는 할인 배열의 처음 10개 항목에 대해 각 제품의 빈도수를 계산한 뒤, 이 빈도수가 정현이가 원하는 제품의 수량과 동일한지 비교한다. 만약 하나라도 수량이 맞지 않거나 원하는 제품이 빠져있다면, 해당 구간은 조건을 만족하지 않는다.
그 후 슬라이딩 윈도우 기법을 사용하여 구간을 한 칸씩 이동시키는데, 구간에서 빠지는 첫 번째 항목의 빈도수는 감소시키고 새로 들어오는 항목의 빈도수는 증가시킵니다. 업데이트된 구간의 제품 빈도수가 목표 맵과 일치하는지 매번 확인합니다. 이렇게 하여 모든 가능한 10일간의 구간을 탐색한 뒤, 조건에 맞는 구간의 수를 결과로 반환하면 됩니다. 만약 조건을 만족하는 구간이 하나도 없다면 0을 반환한다.
이 방법을 사용하면 할인 제품 배열의 길이가 크더라도 각 구간을 효율적으로 업데이트하며 문제를 해결할 수 있다.
import java.util.HashMap;
import java.util.Map;
public class DiscountEvent {
public int solution(String[] want, int[] number, String[] discount) {
int answer = 0;
Map<String, Integer> wantMap = new HashMap<>();
for (int i = 0; i < want.length; i++) wantMap.put(want[i], number[i]);
Map<String, Integer> currentMap = new HashMap<>();
for (int i = 0; i < 10; i++) currentMap.put(discount[i], currentMap.getOrDefault(discount[i], 0) + 1);
if (isSubset(wantMap, currentMap)) answer++;
for (int i = 10; i < discount.length; i++) {
String removeItem = discount[i - 10];
if (currentMap.get(removeItem) == 1) {
currentMap.remove(removeItem);
} else {
currentMap.put(removeItem, currentMap.get(removeItem) - 1);
}
String addItem = discount[i];
currentMap.put(addItem, currentMap.getOrDefault(addItem, 0) + 1);
if (isSubset(wantMap, currentMap)) answer++;
}
return answer;
}
private boolean isSubset(Map<String, Integer> wantMap, Map<String, Integer> currentMap) {
for (Map.Entry<String, Integer> entry : wantMap.entrySet()) {
if (currentMap.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
return false;
}
}
return true;
}
}