131127 - 할인 행사

info

• 문제 보기: 131127 - 할인 행사
• 소요 시간: 35분 15초
• 풀이 언어: java
• 체감 난이도: 2️⃣ (2.2)
• 리뷰 횟수: ✅

풀이 키워드

스포주의

완전탐색 해시 슬라이딩 윈도우

풀이 코드

info

• 메모리: 120000 KB
• 시간: 47 ms

import java.util.*;

class Solution {  
    public int solution(String[] want, int[] number, String[] discount) {
        Map<String, Integer> wantMap = new HashMap<>();
        Map<String, Integer> availMap = new HashMap<>();
        int satisfied = 0; // if satisfied == want.length then ans+=1
        int ldx = 0;
        int rdx = 9; // sum(number) is 10
        int ans = 0;
        
        // init wantMap
        for (int i = 0; i < want.length; ++i) {
            String item = want[i];
            int val = number[i];
            wantMap.put(item, val);
        }
        
        // init availMap
        for (int i = ldx; i < rdx+1; ++i) {
            String dItem = discount[i];
            availMap.merge(dItem, 1, Integer::sum);
            if (availMap.get(dItem) == wantMap.get(dItem)) {
                satisfied += 1;
            }
        }
        if (satisfied == want.length)
            ans += 1;
        
        // slide: window size = 10
        while (rdx < discount.length-1) {
            String lItem = discount[ldx];
            String rItem = discount[rdx+1];
                
            // calculate map & counter
            availMap.merge(lItem, -1, Integer::sum);
            if (availMap.get(lItem) == wantMap.getOrDefault(lItem, 0) - 1)
                satisfied -= 1;
            ++ldx;
            availMap.merge(rItem, 1, Integer::sum);
            if (availMap.get(rItem) == wantMap.getOrDefault(rItem, 0))
                satisfied += 1;
            ++rdx;
            
            if (satisfied == want.length)
                ans += 1;
        }
        
        return ans;
    }
}

풀이 해설

문제 조건에서 number 원소의 합이 항상 10이래서 고정 크기 범위로 스캔하는 슬라이딩 윈도우가 떠올랐다.

wantMap은 그냥 want와 number를 해싱한 것이고

availMap은 $[ldx, rdx]$ 구간의 할인 품목과 그 수를 나타낸다.

📌 Preprocess

// init availMap
for (int i = ldx; i < rdx+1; ++i) {
    String dItem = discount[i];
    availMap.merge(dItem, 1, Integer::sum);
    if (availMap.get(dItem) == wantMap.get(dItem)) {
        satisfied += 1;
    }
}
if (satisfied == want.length)
    ans += 1;

일단 ldx, rdx가 시작부터 0, 9로 세팅되어있으므로 availMap도 이 세팅에 맞추어 사전에 한번 계산해준다.

여기서 작은 최적화를 하나 했는데, 정답일로 카운팅해야 하는 상황에서 wantMap과 availMap이 서로 같은지 확인하는 대신

satisfied라는 카운터 변수를 따로 두고 이게 원하는 품목의 종류 개수와 같은지를 비교했다.

info

satisfied 카운터 조작 방식

satisfied는 슬라이딩 윈도우 로직 내에서 특정 시점에만 조작되는데 해당 시점은 다음과 같다.

• 어떠한 품목이 want를 못 만족하다가 -> 만족하게 됨 (+1)
• 어떠한 품목이 want를 만족하다가 -> 못 만족하게 됨 (-1)

다시 말해 state가 변하는 찰나에만 카운터를 조작해준다.

그러면 모든 품목이 만족했을 땐 카운터가 want의 품목 종류 개수와 같을 것이고, 그게 아니라면 같지 않을 것이다.

📌 Sliding Window

// slide: window size = 10
while (rdx < discount.length-1) {
    String lItem = discount[ldx];
    String rItem = discount[rdx+1];
        
    // calculate map & counter
    availMap.merge(lItem, -1, Integer::sum);
    if (availMap.get(lItem) == wantMap.getOrDefault(lItem, 0) - 1)
        satisfied -= 1;
    ++ldx;
    availMap.merge(rItem, 1, Integer::sum);
    if (availMap.get(rItem) == wantMap.getOrDefault(rItem, 0))
        satisfied += 1;
    ++rdx;
    
    if (satisfied == want.length)
        ans += 1;
}

슬라이딩 윈도우는 다음의 순서로 수행한다.

1. 구간에 들어오거나 밖으로 나가는 품목에 맞추어 availMap 수정
2. 방금 그 품목들에 state 변화가 있는지 체크 (= satisfied를 조작해야되는 조건인지)
3. 구간 경계 인덱스 조정
4. 정답일이면 +1 카운트

여기서 getOrDefault는 자바가 해싱되지 않은 key로 접근하려들면 Exception을 뿜어서(...) 사용한 것이다.

(want의 품목 종류 <= 모든 행사 품목 종류) 라서 wantMap을 존재하지 않는 key로 접근하는 상황이 있기 때문이다.

메모

• 투포인터 아님! 투포인터는 윈도우 크기가 가변적이다.
• 파이썬 딕셔너리 쓰다가 자바 해시맵 쓰니까 눈물이 또 나오려고 한다...
• 돌려보고 WA 뜨면 디버깅할라 했는데 1트 제출 컷해서 당황함