[프로그래머스 lv2] 할인 행사

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

 

 

---

첫번째 풀이 (성공)

10개씩 나눈 뒤에  (주의 <= discount.length-10 = 포함함)

해쉬로 갯수 정리하고 

각기 갯수 비교

 

// 10개씩 나눈 뒤 매칭되나 확인
function solution(want, number, discount) {
    var answer = 0;
    const obj = {};
    for (let i = 0 ;i < want.length; i++) {
        obj[want[i]] = number[i];
    }
    
    function isMatch (arr) {
        const hash = {};
        // 선택된 10개 hash로 각기 갯수 정리
        arr.forEach(a => hash[a] = (hash[a] || 0) + 1);
        // 원하는 품목과 선택된 품목의 갯수 비교
        for (const [key, value] of Object.entries(hash)) {
            if (!obj[key] || hash[key] !== obj[key]) {
                return false;
            }
        }
        return true;
    }    
    
    for (let i = 0; i <= discount.length-10; i++) {
        const selection = discount.slice(i, i+10);
        // 매칭될때
        if (isMatch(selection)) answer++;
    }
    return answer;
}

 

두번째 풀이 (성공)

// 10개씩 나눈 뒤 매칭되나 확인
function solution(want, number, discount) {
    var answer = 0;
    const wantObj = {};
    for (let i = 0; i < want.length; i++) {
        wantObj[want[i]] = number[i];
    }
    for (let i = 0; i <= discount.length-10; i++) { // =
        const selection = discount.slice(i, i+10);
        const selectionObj = {};
        
        selection.forEach(s => selectionObj[s] = (selectionObj[s] || 0) + 1);
        
        // 종류 가짓수가 다르면 패스
        if (Object.keys(selectionObj).length !== want.length) continue;
        
        // 종류별 갯수가 같은지 비교
        let isSame = true;
        for (const [key, value] of Object.entries(selectionObj)) {
            // 틀리면 
            if (value !== wantObj[key]) {
                isSame = false;
                break;
            }
        }
        // 같음
        if (isSame) {
            answer++;
        }
    }
    return answer;
}

 

 

세번째 풀이

할인 제품은 하루에 하나씩만 구매
모두 할인 받을 수 있는 날짜의 총 수를 리턴, 없음 0
nlogn

 

10개의 윈도우를 순회하며 살 수 있으면 answer++한다

 

이렇게 하면

윈도우를 순회하며 윈도우 맨앞의 값은 제거하고 윈도우 맨 뒤 다음을 추가함으로써 매번 10개를 선택할 필요없다

// 슬라이딩 윈도우
function solution(want, number, discount) {
    var answer = 0;
    const obj = {};
    want.forEach((w, i) => {
        obj[w] = number[i];
    })
    const window = {};
    for (let i = 0; i < 10; i++) {
        const curr = discount[i];
        window[curr] = (window[curr] || 0) + 1;  
    }
    if (canBuyAll()) answer++;
    for (let i = 1; i <= discount.length-10; i++) {
        const toDelete = discount[i-1];
        const toAdd = discount[i+9];
        
        if (window[toDelete] === 1) {
            delete window[toDelete];
        } else {
            window[toDelete]--;
        }
        window[toAdd] = (window[toAdd] || 0) + 1;
        
        if (canBuyAll()) answer++;
    }
    
    function canBuyAll() {
        for (const [key, value] of Object.entries(obj)) {
            if (window[key] && value <= window[key]) continue;
            else {
                return false;
            }
        }
        return true;
    }
    return answer;
}