[프로그래머스] 롤케이크 자르기

아래 프로그래머스 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

구현 아이디어는 다음 로직을 따라가면 된다.
1. 전체 토핑 빈도를 Counter로 센다. (오른쪽 조각 초기 상태)
2. 왼쪽은 비어 있는 set으로 시작한다.
3. 왼쪽으로 한 개씩 토핑을 옮기면서

• 왼쪽 set에 토핑 추가
• 오른쪽 dict에서 해당 토핑 개수 감소 → 개수가 0이면 삭제

4.왼쪽과 오른쪽의 set 길이 비교

여담으로 ,,, 파이썬으로는 금방 풀었는데 .. 자스로 푸는게 꽤 손이 많이 갔다.
원래 마지막 if문을 if(left.size === Object.keys(right).length) result++; 이런식으로 갔는데 이거때문에 시간초과가 나는 것 같았다.

왜냐면,, 매번 반복마다 전체 right 객체의 키를 배열로 만들고 길이를 세는 연산 자체가 오래 걸리는것같아서 아예 저 길이를 직접 변수로 관리해버렸다. 그랬더니 통과 ~

코드

---

1. Python

from collections import Counter

def solution(topping):
    result = 0
    right = Counter(topping)
    left = set()

    for t in topping:
        left.add(t)
        right[t] -= 1
        
        if right[t] == 0:
            del right[t]
            
        if len(left) == len(right):
            result += 1
    return result

2. JS

function solution(topping) {
    let result = 0;
    
    const left = new Set();
    const right = {};
    let rightCnt = 0;
    
    for(const t of topping){
        if(!right[t]) rightCnt++;
        right[t] = (right[t] || 0) + 1;
    }
    
    for(const t of topping){
        left.add(t);
        
        right[t]--;
        if(right[t] === 0) rightCnt--;
        if(left.size === rightCnt) result++;
    }
    return result;
}

결과

---