[JS] 롤케이크 자르기

 

 

난이도: Lv. 2

정답률: 57%

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

프로그래머스

 

 

알고리즘

1. 토핑 종류당 개수가 몇 개 있는지에 대한 Map을 초기화한다.

2. 동생 롤케이크의 토핑 종류를 저장하는 Set을 선언한다.

3. 주어진 토핑 배열 topping의 맨 끝 원소부터 하나씩 2.의 Set에 담고, 1.의 Map의 해당 key의 value를 1 감소시킨다. value가 0이 되는 경우 key를 삭제한다.

4. topping 배열을 순회하며 3의 과정을 반복하고, 반복하는 도중에 Map의 size와 Set의 size가 같아지는 경우 정답을 1 증가시킨다. Set의 size가 Map의 size보다 큰 경우부터는 더 이상 정답의 가능성이 없으므로 반복문을 break 한다.

 

 

코드

function solution(topping) {
    let answer = 0;
    const toppingMap = new Map();
    const brotherSet = new Set();

    for (let t of topping) {
        if (toppingMap.has(t)) {
            toppingMap.set(t, toppingMap.get(t) + 1);
        } else {
            toppingMap.set(t, 1);
        }
    }

    for (let i = topping.length - 1; i >= 0; i--) {
        const tp = topping[i];
        const getTp = toppingMap.get(tp);

        brotherSet.add(tp);
        if (getTp === 1) {
            toppingMap.delete(tp);
        } else {
            toppingMap.set(tp, getTp - 1);
        }

        if (brotherSet.size === toppingMap.size) { answer++; }
        else if (brotherSet.size > toppingMap.size) { break; }
    }

    return answer;
}

 

 

주저리

처음에는 Set으로만 풀었는데 시간이 박살 났다. 주어진 토핑 배열을 복사하고 복사본에서 하나씩 pop()해서 동생 롤케이크 Set에 넣어주고 복사본을 Set으로 만들어 두 Set의 크기가 일치하는지 확인했는데 할 때마다 배열을 Set으로 만들어서 시간이 박살 난 것 같다.

function solution(topping) {
    let answer = 0;
    const toppingCopy = [...topping];
    const set1 = new Set();
    const toppingSet = new Set(topping);
    const minTopping = Math.ceil(toppingSet.size / 2);

    while (toppingCopy.length) {
        set1.add(toppingCopy.pop());

        if (set1.size >= minTopping) {
            const set2 = new Set(toppingCopy);
            if (set1.size === set2.size) { answer++; }
            else if (set1.size > set2.size) { break; }
        }
    }

    return answer;
}

아무리 생각해도 Set으로 푸는 문제인데 도저히 모르겠어서 질문하기 들어갔다가 제목에 Map 풀이라는 거 보고는 안 보고 나와서 Map으로 해서 쉽게 풀었다. 왜 Map으로 풀 생각은 못했을까 바보아녀?