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

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(topping) {
    const left = {};
    const right = topping.reduce((acc, v) => {
        acc[v] = (acc[v] ?? 0) + 1;
        return acc;
    }, {});
    
    let leftCount = 0;
    let rightCount = new Set(topping).size;
    let answer = 0;
    
    for (let i = 0; i < topping.length - 1; i++) {
        const curTopping = topping[i];
        if (!left[curTopping]) {
            leftCount++;
        }
        left[curTopping] = (left[curTopping] ?? 0) + 1;
        
        right[curTopping]--;
        if (!right[curTopping]) {
            rightCount--;
        }
        
        if (leftCount === rightCount) {
            answer++;
        }
    }
    
    return answer;
}

처음에 한 사람이 모든 케이크를 다 갖고 있고, 거기서 한 조각씩 왼쪽부터 떼어준다는 가정을 하고 left와 right에 현재 갖고 있는 토핑의 개수를 저장하였다. left는 처음에 한 조각도 갖고 있지 않기 때문에 비어 있고, right에는 모든 토핑의 종류별 개수가 저장되어 있다.

 

이 상태에서 topping을 순회하면서 각 토핑을 left에 추가하고 right에서는 빼는 과정을 반복한다. 이 때 leftCount와 rightCount로 현재 보유한 토핑 종류의 개수를 갱신한다. 토핑 종류의 개수는 Object.keys(left).length, Object.keys(right).length를 매번 구해서 비교하면 비효율적이기 때문에 따로 변수를 만들어서 갱신하였다. 토핑 종류의 개수가 같아질 때마다 answer를 증가시키면 케이크를 자르는 모든 방법의 개수를 구할 수 있다.

 

 

단순히 순회를 하면서 new Set(slice(0, i + 1))과 new Set(slice(i + 1))의 size를 비교하게 되면 Set을 만드는데 O(n)이 소요되므로 O(n^2)가 되어 시간 초과가 난다. 따라서 해시 테이블을 사용해서 시간을 단축해야 통과할 수 있다.