[Javascript] 실전 대비 모의고사 2차 2번

topping 배열이 주어지고 A와 B가 topping을 나눠 갖을때
A와 B가 같은 수의 topping 종류를 갖는 경우의 수를 return하는 문제이다.

[4, 3, 4, 5, 4, 5, 3, 4]라는 topping이 주어지면
1. [4, 3, 4, 5, 4] [5, 3, 4] 로 한가지 경우
2. [4, 3, 4, 5] [4, 5, 3, 4] 로 한가지 경우
총 두가지가 있다.

접근 방법

HashTable을 사용하여 두 Map의 크기가 같을 때를 체크하는 방향으로 접근하였다.

1. 우선 topping의 모든 정보를 갖는 Map을 구한다.

const baseMap = new Map();

for(const t of topping){
    if(!baseMap.has(t)){
        baseMap.set(t, 1);
    }else{
        baseMap.set(t, baseMap.get(t) + 1);
    }
}​

2. topping을 다른 Map에 topping의 정보를 담고, 기존 Map에 해당 topping의 정보를 빼면서 순회한다.

while(true){
    const t = topping.pop();

    baseMap.set(t, baseMap.get(t) - 1);
    if(baseMap.get(t) === 0) baseMap.delete(t);

    if(!subMap.has(t)){
        subMap.set(t, 1);
    }else{
        subMap.set(t, subMap.get(t) + 1);
    }

    if(baseMap.size === subMap.size){
        answer++;
    }else if(baseMap.size < subMap.size){
        break;
    }
}

baseMap.get(t) === 0 일때 제거하는 부분이랑

while문의 종료 조건을 주의해야한다.

 

function solution(topping) {
    var answer = 0;

    const baseMap = new Map();
    const subMap = new Map();

    for(const t of topping){
        if(!baseMap.has(t)){
            baseMap.set(t, 1);
        }else{
            baseMap.set(t, baseMap.get(t) + 1);
        }
    }

    while(true){
        const t = topping.pop();

        baseMap.set(t, baseMap.get(t) - 1);
        if(baseMap.get(t) === 0) baseMap.delete(t);

        if(!subMap.has(t)){
            subMap.set(t, 1);
        }else{
            subMap.set(t, subMap.get(t) + 1);
        }

        if(baseMap.size === subMap.size){
            answer++;
        }else if(baseMap.size < subMap.size){
            break;
        }
    }
    
    return answer;
}