Level 2️⃣ - 롤케이크 자르기

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

프로그래머스

 

🚀문제 해석

올려진 토핑의 갯수와 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하다고 생각한다.

즉, 1 1 3 4 | 2 3 4 이렇게 나누어도 각 조각의 토핑의 가짓수는 각각 3개씩이므로 공평하다고 생각하는 것이다. 

토핑의 가짓수만 확인한다는 것은 중복을 생각하지 않고 오직 토핑의 종류만 생각한다는 것이다.

먼저 입력값이 최악의 경우 100만이기 때문에 이중 for문으로 접근할 시 O(N^2)이 되므로 실패할 것이라 예상했다.

따라서 Map을 활용해 모든 토핑 종류의 갯수를 다 카운팅한 다음에 케이크를 하나씩 자르면서 토핑 종류의 갯수를 비교하고자 한다.

 

코드

결국 토핑을 순회하며 케이크를 자르는 로직에서 O(N)만큼의 시간복잡도를 만드는 것이 관건이었는데 해시맵을 활용하니 가능해졌다. 그리고 각 해시맵의 키값들의 갯수만 확인하는 이유는 앞서 언급한 것처럼 토핑 종류의 갯수만 확인하기 위해서이다.

function solution(topping) {
    let toppingCount = new Map();
    let cut = new Map();
    topping.forEach((num)=>{
        if(toppingCount.has(num)) toppingCount.set(num, toppingCount.get(num) + 1);
        else toppingCount.set(num, 1);
    });
    let n = toppingCount.size;
    let m = 0;
    let ret = 0;
    
    topping.forEach((num)=>{
        if(cut.has(num)) cut.set(num, cut.get(num) + 1);
        else {
            cut.set(num, 1);
            m++;
        }
        toppingCount.set(num, toppingCount.get(num) - 1);
        if(toppingCount.get(num) === 0){
            toppingCount.delete(num);
            n--;
        }
        if(m === n) ret++;
    });
    return ret;
}