할인 행사

사용 알고리즘: 슬라이딩 윈도우...?

사용 언어: java

 

처음엔 문제를 잘못 이해해서 틀렸다. 처음 회원 등록이 가능한 날을 리턴하는 것인줄..ㅎㅎ

아래는 틀린 코드!

import java.util.*;

class Solution {
    Map<String, Integer> map = new HashMap<>();
    Map<String, Integer> jun = new HashMap<>();
    
    public int solution(String[] want, int[] number, String[] discount) {
        init(want, number);
        
        int answer = 1;
        boolean beMember = false;
        
        for (int i = 0; i < 10; i++) {
            map.put(discount[i], map.getOrDefault(discount[i], 0) + 1);
        }
        
        int beforeLast = 0;
        int newLast = 10;
        while(newLast < discount.length) {
            if(canBeMem()) {
                beMember = true;
                return answer;
            }
            
            answer++;
            slidingWindow(discount, beforeLast, newLast);
            beforeLast++;
            newLast++;
        }
        
        // System.out.println(map);
        
        if(!beMember) return 0;
        return answer;
    }
    
    public void slidingWindow(String[] discount, int bl, int nl) {
        //bl빼고
        //nl넣고
        // System.out.println("A");
        map.put(discount[bl], map.get(discount[bl]) - 1);
        map.put(discount[nl], map.getOrDefault(discount[nl], 0) + 1);
        if(map.get(discount[bl]) == 0) map.remove(discount[bl]);
    }
    
    public boolean canBeMem() {
        for(String key : map.keySet()) {
            if(!jun.containsKey(key))
                return false;
            if(jun.get(key) != map.get(key))
                return false;
        }
        return true;
    }
    
    public void init(String[] want, int[] number) {
        for(int i=0; i<want.length; i++) {
            jun.put(want[i], number[i]);
        }
    }
}

 

 

회원 등록이 가능한 전체 날짜의 개수를 구하는 것이다.

import java.util.*;

class Solution {
    Map<String, Integer> jeongHyun = new HashMap<>();
    Map<String, Integer> discounts = new HashMap<>();
    
    public int solution(String[] want, int[] number, String[] discount) {
        for(int i=0; i<want.length; i++) {
            jeongHyun.put(want[i], number[i]);
        }
        
        int answer = 0;
        for(int i=0; i<discount.length; i++) {
            if(i < 10) {
                discounts.put(discount[i], discounts.getOrDefault(discount[i], 0) + 1);
                if(i == 9) {
                    if(registerMember()) {
                        answer++;
                    }
                }
                continue;
            }
            
            int removeIdx = i - 10;
            discounts.put(discount[removeIdx], discounts.get(discount[removeIdx]) - 1);
            discounts.put(discount[i], discounts.getOrDefault(discount[i], 0) + 1);
            
            if(registerMember())
                answer++;
        }
        
        return answer;
    }
    
    public boolean registerMember() {
        for(String key : jeongHyun.keySet()) {
            if(!discounts.containsKey(key))
                return false;
            if(jeongHyun.get(key) != discounts.get(key))
                return false;
        }
        return true;
    }
}

 

 

나는 슬라이딩 윈도우처럼 구현하고 싶어서,

discount가 11번 째일 때부터는 앞의 품목을 빼고, 새로운 품목을 더하면서 계산했다.

 

그런데 굳이 슬라이딩 윈도우를 하지 않아도 시간 초과가 나지 않는다...ㅎ...ㅎ