[연습문제] PGS lv2. 롤케이크 자르기

 

- 토핑이 순서대로 올려진 케이크를 한조각 한조각, 둘로 잘라서 똑같은 토핑의 종류의 수가 되게하는 경우의수.

 

첫 시도는 그냥 배열 쭈욱 돌면서 좌, 우 slice, -> set 해서 토핑의 종류의 개수를 찾았는데 이렇게하니 시간초과가 뜸

-> 해시맵으로 처음에 오른쪽 케이크를 구해놓고 왼쪽케이크에 옮겨가면서 매 for문을 돌때 slice, set을 안하도록 수정

 

function solution(topping) {
    let result = 0;
    const map = new Map();
    const set = new Set(topping.slice(0,1));
    const arr2 = topping.slice(1);
    arr2.forEach((num)=>{
        const count = (map.get(num) ||0);
        map.set(num, count+1);
    })
    
    for(let i=1;i<topping.length-1;i++){
        set.add(topping[i])
        const count = map.get(topping[i])
        if(count-1 ===0){
            map.delete(topping[i])
        }
        if(count-1>0){
            map.set(topping[i],count-1 )
        }
        if(set.size===map.size) result +=1; 
    }
    return result;
}