프로그래머스 Lv.2 롤케이크자르기

💁🏻 코드

function solution(topping) {
    const bro = new Map();
    const tpInfo = new Map();
    topping.forEach(tp => tpInfo.set(tp, (tpInfo.get(tp) || 0) + 1));
    
    let answer = 0;
    for (let tp of topping) {
        // ✅ 토핑을 하나씩 확인하면서 해당 토핑 개수를 하나씩 빼준다 (=케익 자르기)
        tpInfo.set(tp, tpInfo.get(tp) - 1);
        // ✅ 롤 케이크에 해당 토핑의 개수가 0인 경우
        if (!tpInfo.get(tp)) tpInfo.delete(tp);
        // ✅ 토핑 종류의 개수는 중요하지 않다 (존재 여부가 중요하기 때문)
        bro.set(tp, true);
        // ✅ 형과 동생 케이크 각각의 토핑 종류 개수를 비교한다
        if (tpInfo.size === bro.size) answer++;
        // ✅ 형의 케이크 토핑 종류가 더 많아지는 경우
        else if (tpInfo.size < bro.size) break;
    }
    return answer;
}

입력값의 제한은 다음과 같습니다.

• 1 <= 토핑들의 번호가 담긴 배열 topping <= 1,000,000

topping 배열에 대해서 이중 for문을 돌리는 건 무리가 있다고 생각했습니다.
그래서 시간복잡도가 O(n)인 완전탐색으로 접근을 시도했습니다.
로직은 애초에 모든 토핑이 나의 것으로 생각하고 전개했습니다.
topping 배열을 앞에서부터 하나씩 살펴보면서 뒤로 이동해 동생의 토핑 종류를 늘리는 식입니다.
Map 자료형을 사용한 이유는 { 토핑 번호 : 개수 } 형태로 데이터를 관리하기 위해서입니다.
핵심은 동생이 가지게 되는 토핑 종류 개수가 더 많아지는 경우 반복문을 종료하는 것입니다.
동생이 가지게 되는 토핑 종류가 많아지는 순간부터는 내가 더이상 동생보다 많은 종류의 토핑을 가질 수 없기 때문입니다.
참고로 동생이 가지게 될 토핑의 종류는 { 토핑 번호: 개수 }의 형태가 아닌 { 토핑 번호: true } 형태입니다.
동생이 어떤 종류의 토핑을 몇 개 갖는 건 중요하지 않고 그냥 가지고 있다는 사실 자체가 중요하기 때문입니다.