할인 행사

문제

일정 금액을 지불하면 10일 동안 회원 자격을 부여하는 마트가 있습니다. 이 마트에서는 회원을 대상으로 매일 한 가지 제품을 할인하는 행사를 합니다. 정현이는 자신이 원하는 제품과 수량이 마트에서 할인하는 날짜와 10일 연속으로 일치할 경우에 맞춰서 회원가입을 하려 합니다. 원하는 제품을 나타내는 문자열 배열 want와 수량을 나타내는 정수 배열 number, 마트에서 할인하는 제품을 나타내는 문자열 배열 discount가 주어졌을 때, 회원등록시 정현이가 원하는 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수를 반환하는 문제입니다.

• 입력: 원하는 제품 배열 want, 제품의 수량 배열 number, 마트 할인 제품 배열 discount (길이 10 이상 100,000 이하)
• 출력: 조건을 만족하는 회원등록 날짜의 총 일수 (가능한 날이 없으면 0 반환)

링크: https://school.programmers.co.kr/learn/courses/30/lessons/131127

풀이: HashMap과 슬라이딩 윈도우(Sliding Window)를 활용한 최적화

회원 자격이 주어지는 '10일'이라는 고정된 구간을 탐색하는 문제입니다. 매번 10일 치의 할인 품목을 새로 세어본다면 O(N * 10)의 시간이 걸리지만, 슬라이딩 윈도우 기법을 사용하면 구간을 한 칸씩 밀면서 빠지는 항목과 새로 들어오는 항목만 갱신하여 연산을 최소화할 수 있습니다.

• 초기 윈도우 설정: 먼저 0일 차부터 9일 차까지 처음 10일 동안의 할인 품목을 HashMap에 담고 빈도수를 카운트합니다.
• 조건 검사 (check 메서드): 현재 맵에 담긴 10일 치의 품목들이 정현이가 원하는 품목(want)과 수량(number)을 모두 만족하는지 확인합니다. 맵에 품목이 없거나, 수량이 부족하면 false를 반환합니다.
• 슬라이딩 윈도우 이동: 10일 차부터 discount 배열의 끝까지 순회하며 윈도우를 오른쪽으로 한 칸씩 이동시킵니다.
  • 빠지는 품목 제거: 윈도우의 가장 왼쪽에서 벗어나는 품목(discount[i - 10])의 빈도수를 맵에서 1 감소시킵니다.
  • 새로운 품목 추가: 윈도우의 가장 오른쪽에 새롭게 들어오는 품목(discount[i])의 빈도수를 맵에 추가하거나 1 증가시킵니다.
• 매번 윈도우가 이동할 때마다 check 메서드를 호출하여 조건을 만족하는지 확인하고 정답(ans)을 갱신합니다.

코드

import java.util.*;

class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        int ans = 0;
        
        Map<String, Integer> map = new HashMap<>();
        
        // 1. 처음 10일 치 할인 품목으로 초기 윈도우 구성
        for (int i = 0; i < 10; i++) {
            String s = discount[i];
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        
        // 초기 윈도우 조건 확인
        if (check(map, want, number)) {
            ans++;
        }
        
        // 2. 슬라이딩 윈도우 이동 (한 칸씩 밀기)
        for (int i = 10; i < discount.length; i++) {
            // 윈도우에서 빠지는 이전 품목 제거
            String p = discount[i - 10];
            map.put(p, map.get(p) - 1);
            
            // 윈도우에 새롭게 들어오는 품목 추가
            String s = discount[i];
            map.put(s, map.getOrDefault(s, 0) + 1);
            
            // 갱신된 윈도우 조건 확인
            if (check(map, want, number)) {
                ans++;
            }
        }
        
        return ans;
    }
    
    // 현재 윈도우의 품목들이 원하는 조건을 만족하는지 검사하는 메서드
    boolean check(Map<String, Integer> map, String[] want, int[] number) {
        for (int i = 0; i < want.length; i++) {
            String s = want[i];
            // 원하는 품목이 없거나 수량이 부족하면 false
            if (!map.containsKey(s) || map.get(s) < number[i]) {
                return false;
            }
        }
        
        return true;
    }
}

알고리즘 분류

자료 구조 (Data Structures), 해시를 사용한 맵 (Hash Map), 슬라이딩 윈도우 (Sliding Window)