[Jacoste] 알고리즘 공부

<롤케이크 자르기>는 배열로 주어지는 토핑의 종류를 두 개로 나누었을 때, 각 배열의 토핑 종류 수가 같게 만들어지는 경우의 수를 구하는 문제다.

문제를 보고 처음 한 생각은 배열을 두개로 쪼개서 Set()을 사용하면 종류 수를 구할 수 있겠다!는 것이었다. 그 생각으로 만든 코드가 아래의 코드다.

function solution(topping) {
    let res = 0;
    for (let i = 1; i < topping.length; i++) {
        const cs = topping.slice();
        const ds = cs.splice(i);
        if (new Set(cs).size === new Set(ds).size) res++;
    }
    return res;
}

토핑의 개수만큼 반복문을 돈다. 철수(cs) 배열과 동생(ds) 배열을 만든다. 그리고 slice() 매서드로 철수 배열에 topping을 복사한 뒤, 철수의 topping을 splice() 매서드로 동생 배열에 할당한다. 잘 작동하긴 하지만 반복문을 돌때마다 새로운 배열을 만들기 때문에 효율이 크게 떨어진다.

그래서 생각해낸 방법은 Set()을 사용하는 것이다.

function solution(topping) {
    const cs = new Set();
    const ds = new Set();
    let numCs = Array(topping.length - 1).fill();
    let numDs = Array(topping.length - 1).fill();
    
    for (let i = 0, len = topping.length - 1; i < len; i++) {
        cs.add(topping[i]);
        ds.add(topping[len - i]);
        numCs[i] = cs.size;
        numDs[len - i - 1] = ds.size;
    }
    return numCs.reduce((acc, cur, i) => acc + (cur === numDs[i] ? 1 : 0), 0);
}

반복문을 돌면서 철수와 동생의 객체에 값을 하나씩 추가한다. 철수는 앞에 있는 토핑부터, 동생을 뒤에 있는 토핑부터 하나씩 차례대로 추가하게 되는데, 이때 토핑 종류의 개수를 알기 위해 .size 메서드를 사용한다.

5개의 토핑 중 철수가 1개의 토핑을 받았을 때 동생은 5-1개의 토핑, 즉 4개의 토핑을 받게 된다. 때문에 철수의 토핑 종류의 개수를 저장하는 numCs 배열은 앞에서부터 저장했고, 동생 토핑 종류의 개수를 저장하는 numDs 배열은 뒤에서부터 저장했다.

마지막으로 reduce() 메서드를 돌면서 numCs[i]와 numDs[i]가 같을 때의 경우를 센다. 원래 filter() 메서드를 사용했는데, 실행 결과 reduce()가 더 빨라서 바꾸게 되었다.