[JS/Programmers] 131127. 할인행사

💬 문제

문제 난이도: Programmers Lv.2

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

❗️접근 방법

효율성을 높일 수 있는 방법을 고민하다 '일단 정확하게 돌아가는 코드'를 짜보았다.
그리고 최대한 순회하는 비용을 줄이기 위해 for문 종료 조건을 discount.length - totalNum으로 수정했다.
1~2차 코드에 비해 3차 코드의 효율(시간)이 높았던 이유는 주어진 arr를 obj형으로 수정하지 않았다는 점이다.
1~2차 코드에서는 arr를 모두 순회하며 해당 value가 몇 번 등장했는지를 저장하는 obj를 만들었다.
3차 코드에서는 sort함수를 활용해 want 배열과 tmp 배열의 원소가 같은지 비교하는 방식으로, 즉 obj를 만들지 않았다.
위와 같은 방식이 가능했던 점은 want, tmp 배열의 길이가 최대 10이었기 때문에 sort 연산을 위한 시간이 길지 않았기 때문이다.
그리고 문제의 조건이 원하는 개수 <= 구매 가능한 개수가 아니라, 원하는 개수 === 구매 가능한 개수였기 때문에 두 배열을 비교해서 같으면 answer++하는 식으로 풀 수 있었다.

👆 1차 코드

function solution(want, number, discount) {
    let answer = 0;
    const totalNumber = number.reduce((acc, cur)=>acc + cur, 0);
    for (let i = 0; i <= discount.length-totalNumber; i+= 1){
        const maxI = (i+10>discount.length) ? discount.length : i+ 10;
        const subArr = discount.slice(i, maxI);
        const obj = {};
        for (let j = 0; j < subArr.length; j+=1){
            if (obj.hasOwnProperty(subArr[j])) obj[subArr[j]] += 1;
            else obj[subArr[j]] = 1; 
        }
        let flag = true;
        for (let j = 0; j < want.length; j+=1){
            if (obj.hasOwnProperty(want[j]) && obj[want[j]]>=number[j]) continue;
            else{
                flag = false;
                break;
            }
        }
        if (flag) answer += 1
    }
    return answer;
}

✌️ 2차 코드 (기능 단위로 분리)

function getCntObj(arr){
    const obj = {};
    for (let j = 0; j < arr.length; j+=1){
            if (obj.hasOwnProperty(arr[j])) obj[arr[j]] += 1;
            else obj[arr[j]] = 1; 
        }
    return obj;
}

function isAnswer(obj, want, number){
    for (let i = 0; i < want.length; i+= 1){
        if (!obj.hasOwnProperty(want[i]) || obj[want[i]] < number[i]) return false;
    }
    return true;
}

function solution(want, number, discount) {
    let answer = 0;
    
    /* 적어도 discount에 남은 product의 개수가 number 총 합보다는 많거나 같아야 한다.
        따라서 reduce를 사용해 number의 총합을 구했다.
        그리고 discount 배열을 순회할 때 전체를 돌지 않고 i <= discount.length - totalNumber으         로 for문 종료 조건을 정했다.
    */

    const totalNumber = number.reduce((acc, cur)=>acc + cur, 0);
    for (let i = 0; i <= discount.length - totalNumber; i+= 1){
        const maxI = (i+10>discount.length) ? discount.length : i+ 10;
        const subArr = discount.slice(i, maxI);
        const obj = getCntObj(subArr);
        
        if (isAnswer(obj, want, number)) answer += 1
    }
    return answer;
}

🤟 3차 코드 (다른 사람 풀이 참고)

function solution(want, number, discount) {
    const totalNum = number.reduce((acc, cur)=>acc+cur, 0);
    let wantArr = []
    let answer = 0;
    for (let i = 0; i < want.length; i+=1){
        for (let j = 0; j < number[i]; j+=1)
            wantArr.push(want[i]);
    }
    wantArr.sort();
    for (let i = 0; i<= discount.length-totalNum; i+=1){
        
        /*Array.prototype.slice(start, end)
            end가 array 길이보다 크다면 배열의 끝까지만 추출한다.
            따라서 알아서 아래의 비교문은 필요 없다.
        */
        // const maxI = (i+10>discount.length) ? discount.length : i+10;
        const tmp = discount.slice(i, i+10).sort();
        /* js에서 두 배열을 비교하는 방법
            1. arr1.toString() === arr2.toString()
            2. JSON.stringify(arr1) === JSON.stringify(arr2)
        */
        /* 문제에서 "10일 연속으로 일치할 경우"라고 적혀 있다.
            "원하는 개수 <= 살 수 있는 개수" 가 아니라
            "원하는 개수 === 살 수 있는 개수"이어야 한다.
            따라서 아래의 비교문으로 answer의 개수를 구하면 된다. (문제 좀 잘 읽자.)
        */
        answer += wantArr.toString() === tmp.toString();
    }
    return answer;
}

(참고: https://www.freecodecamp.org/news/how-to-compare-arrays-in-javascript/)
(참고: https://beomcoder.tistory.com/48)

✍️ JS에서 두 배열 비교하기

const arr1 = {name : "Lee"};
const arr2 = {name : "Lee"};
console.log(arr1 === arr2); // false
-> arr1과 arr2은 두 객체가 저장되어 있는 주소값을 저장하고 있다.
-> 즉, 두 변수는 같아 보이지만 실제로 다른 객체를 참조하고 있다.

const arr3 = arr1;
console.log(arr3 === arr1); // true
-> arr1이 가리키고 있는 객체를 arr3도 가리킨다.
-> 즉, 두 변수는 실제로 같은 객체로 참조하고 있다.

JS에서 두 배열이 같은 프로퍼티를 가지고 있는지 확인하려면?
1. JSON.stringify(arr);
2. arr.toString();
-> (JSON) string 타입으로 변환해 비교하면 된다.
-> string은 원시타입이므로 실제 데이터를 저장하므로 === 일치 연산자를 사용해서 비교할 수 있다.