Lv.2 : 할인 행사

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 원하는 물품과 그 개수가 주어진다.
• 각 날짜 별 할인 물품 리스트가 주어진다. 10일 이내에 원하는 물품을 각 개수 이상 살 수 있는 구간의 수를 반환한다.

🔸 문제 풀이 🔸

• 슬라이딩 윈도우 방식으로 10크기의 윈도우를 이동하며 물품 개수를 체크한다.

---

🔸 코드 🔸

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        
        // 입력 문자열 hash로 저장
        int answer = 0;
        int[] cnt = new int[want.length];
        Map<String, Integer> map = new HashMap<>();
        
        for(int i = 0; i < want.length; i++) {
            map.put(want[i], i);
        }
                        
        // 투 포인터 초기화
        int start = 0;
        int end = 9;
        
        for(int i = 0; i < 10; i++) {
            if(map.containsKey(discount[i])) {
                cnt[map.get(discount[i])]++;
            }
        }
        
        // 조건에 맞는지 검사
        if(cntCheck(number, cnt)) answer++;
        
        // 투 포인터 검사
        while(end < discount.length - 1) {
            // 다음 칸 진행
            String ss = discount[start];
            if(map.containsKey(ss) && cnt[map.get(ss)] > 0)
                cnt[map.get(ss)]--;
            
            start++;
            end++;
            
            String es = discount[end];
            if(map.containsKey(es))
                cnt[map.get(es)]++;
            
            // 조건에 맞는지 검사
            if(cntCheck(number, cnt)) answer++;
        }
        
        return answer;
    }
    
    private boolean cntCheck(int[] number, int[] cnt) {
        for(int i = 0; i < number.length; i++) {
            if(cnt[i] < number[i]) {
                return false;
            }
        }
        return true;
    }
}

🔸 코드 해석 🔸

• 물품은 10개지만 빠른 인덱스 찾기를 위해 HashMap에 물품명과 인덱스를 저장했다.
• 윈도우는 int형 배열 cnt로 사용했다.
• 조건에 맞는지 확인은 cntCheck() 메서드로 따로 빼서 진행했다.
• 윈도우가 이동하면서 빠져나간 인덱스의 물품은 -1, 들어온 인덱스의 물품은 +1 해준 뒤 조건에 맞는지 검사한다.
  • 조건에 맞으면 answer를 +1 한다.
• answer를 반환한다.

---

🔸 end 🔸

• 슬라이딩 윈도우로 이해했으면 더 빠르게 풀이했을 것 같은데, 투포인트로 이해해서 풀이하다가 크기가 10으로 고정되어 있다는걸 뒤늦게 파악하고 코드를 수정했다.
• 다른 풀이를 보니, cnt 같은 윈도우 배열을 따로 두는게 아닌, hashmap에 인덱스 대신해서 저장하는 방식의 풀이가 더 효율적인 것 같다.