롤케이크 자르기

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

 

 

 

 

풀이

topping 길이 1,000,000 => O( nlogn )
slice의 시간복잡도는 O(n) => 매번 잘라서 형과 동생의 토핑갯수를 구할 수 없다

처음에 형한테 모든 토핑을 준다

그 후 토핑을 순회하며 동생이 하나씩 가져가고 형과 동생의 토핑갯수를 비교한다.

 

function solution(topping) {
    var answer = 0;
    const old = {}; // 토핑 종류별 갯수
    const young = {};
    let oldCount = 0; // 토핑 종류 갯수
    let youngCount = 0;
    
    topping.forEach(t => {
        if (!old[t]) {
            old[t] = 1;
            oldCount++;
        } else {
            old[t]++;
        }
    })
    
    for (const t of topping) {
        if (!young[t]) {
            young[t] = 1;
            youngCount++;
        } else {
            young[t]++;
        }
        
        // 토핑이 한개 남아있으면 형의 토핑 갯수는 감소한다.
        if (old[t] === 1) {
            oldCount--;
        }
        old[t]--; // 형의 토핑 감소
        
        // 형과 동생의 토핑갯수 비교
        if (oldCount === youngCount) {
            answer++;
        }
    }
    return answer;
}