[JS] 프로그래머스 - 롤케이크 자르기

처음에는 단순하게 slice로 배열을 자른다음 set객체를 이용하여 풀면되겠다는 생각을 하여 코드를 짯고

function solution(topping) {
    var answer = 0;
    let index=1;
    
    while(index!==topping.length){
        
        let person1=topping.slice(0,index);
        let person2=topping.slice(index, topping.length);
        
        let s1=new Set();
        let s2=new Set();
        
        person1.map(v=>{
            s1.add(v);
        })
        person2.map(v=>{
            s2.add(v);
        })
        
        if(s1.size===s2.size){
            answer++;
        }
        index++;
    }
    
    
    return answer;
}

테스트케이스를 통과하였다.

그리고 자신만만하게 제출을 눌렀고
돌아오는건

(역시 ... 너무 쉽게 풀린다 했어...)

힌트를 찾아보니

일단 토핑의 길이가 최대 1,000,000이고 그 안에서 slice함수를 사용하게 된다면 시간복잡도 O(n)이기 때문에 시간 초과가 난다.

그래서 최대한 중첩 반복문 사용을 배제하는 방법으로 사용하였고

function solution(topping) {
    var answer = 0;
    let baseSet=new Set();
    let compareSet=new Set();
    let counter=new Array(10001).fill(0);
    
    if(topping.length===1){
        return answer;
    }
    
    topping.map(v=>{
        baseSet.add(v);
        counter[v]++;
    })
    
    topping.map(v=>{
        if(counter[v]>=1){
            counter[v]--;
        }
        if(counter[v]===0){
            baseSet.delete(v);
        }    
        compareSet.add(v);    
        if(baseSet.size===compareSet.size){
            answer++;
        }
    })
    
    return answer;
}

처음에 전체토핑을 알 수 있는 baseSet과 counter배열을 통해 토핑이 몇개인지 각 토핑이 몇개씩 있는지 저장한다.

그리고 다시 처음부터 돌면서 비교하는 set객체를 만들어 토핑을 넣어주고 counter에서는 각 토핑갯수를 줄여주고 만약 토핑갯수가 0이면 base에서 삭제한다. 마지막으로 base와 compare의 크기가 같다면 answer을 더해주는식으로 코드를 짯다.