프로그래머스 롤케이크 자르기 - 자바스크립트 Map 객체 활용

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

롤케이크 자르기는 1~10,000 중 무작위 수가 담긴 1,000,000 이하의 length를 갖는 배열이 있을 때, 배열을 길이와 상관없이 2등분 하였을 때 총 개수와 상관없이 A와 B의 값이 다른 숫자의 수(Unique Value)가 일치하는 경우의 수를 묻는 문제이다.

O(n²) 시간복잡도 풀이 (시간초과)

function solution(topping) {
    let answer = 0;
    const n = topping.length;
    if(n === 1) return 0;
    for(let i=1; i<n; i++){
        if(new Set(topping.slice(0,i)).size
           === new Set(topping.slice(i)).size) {
            answer++;
        }
    }
    return answer;
}

처음에는 slice를 사용하여 배열을 분할한 뒤 Set을 통해 Unique Value를 파악하였지만 시간초과로 실패하였다.
O(n)의 시간복잡도를 갖는 for문과 slice가 중첩되어 O(n²)의 시간복잡도를 가진다.

O(n)시간복잡도 풀이

function solution(topping) {
    let answer = 0;
    const n = topping.length;
    if(n === 1) return 0;
    
    const A = new Map();
    const B = new Map();
    for(let x of topping){
        B.set(x, (B.get(x) || 0) + 1);
    }
    
    for(let i=0; i<n-1; i++){
        const top = topping[i];
        A.set(top, 1);
        if(B.get(top) === 1) B.delete(top);
        if(B.get(top)) B.set(top, B.get(top)-1);
        if(A.size === B.size) answer++;
    }
    return answer;
}

코드의 흐름은 다음과 같다.

1. B의 토핑 정보를 B 라는 Map 객체에 담는다. → O(n)
2. for문을 사용하여 토핑의 정보를 A에 담고, B에서는 덜어낸다. → O(n)
3. 만약 B의 토핑이 0이라면 delete를 사용하여 토핑의 종류를 감소시킨다. → O(1)
4. Map.size를 통해 A와 B를 비교하여 값이 같다면 answer(경우의 수)를 +1 한다. → O(1)

Object를 사용하여 토핑의 정보를 담으면 종류(Unique Value)를 파악하기 위해 Object.keys()를 사용해야 하는데, 이때 O(n)의 시간복잡도가 걸리기 때문에 O(1)의 시간복잡도를 갖는 Map.size를 사용하기 위해 Map을 선택했다.

또한 아주 약간이지만 Map은 Object보다 메모리를 조금 더 사용하는 대신, 값을 바꿀 때에는 조금 더 좋은 성능을 가지기도 한다.

다른 사람의 풀이

function solution(topping) {
    const a = new Set()
    const b = {}

    let answer = 0;
    let check = 0

    for (let i = 0; i < topping.length; i++) {        
        if (b[topping[i]]) {
            b[topping[i]]++
        } else {
            b[topping[i]] = 1
            check++            
        }
    }

    for (let i = 0; i < topping.length; i++) {
        a.add(topping[i])
        b[topping[i]]--

        if (!b[topping[i]]) check--
        if (a.size === check) answer++
    }

    return answer;
}

가장 많은 좋아요를 받은 jgjgill 님의 풀이이다.
Map을 사용하지는 않았지만, 토핑의 종류(Unique Value)를 check라는 별도의 변수를 두고 계산하였다.

기본적인 흐름은 비슷하지만, Map 보다는 Object가 다루기 쉽고 가독성이 좋다는 점에서 좋은 코드라고 생각한다.