[JS] 2Level / 연습문제 / 롤케이크 자르기

문제 설명

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

프로그래머스

 

문제 풀이 방법

• 이 문제의 제한사항을 보면 매개변수로 주어지는 topping의 길이가 1,000,000까지 인걸 볼 수 있다.
  이는 slice() 메서드나 중첩 for문을 이용할 경우 시간복잡도 O(n)으로 인해 시간초과 에러가 날 수있다.
  종합하자면, 이 문제는 시간복잡도 O(n) 최적화 문제인 것이다.
• 그렇다면 이 문제는 Set()과 slice를 함께 이용해 풀이한는 방식은 안된다는 것이다.
  왜 단정 짓느냐.... 해봤는데 안됬다.
• 유효한 풀이 방법은 Map 객체에 각 토핑의 갯수를 담아주고 Set객체는 topping을 순회하며 넣어주면서, Map 객체에 있는 토핑의 갯수를 줄여가며 문제를 풀어 나갔다.
• 생각해보면 케이크를 자르는 부분을 한칸 한칸 늘려가며 비교하는 방식이다.
  그 방식이 Map에 모든 토핑의 갯수를 담고, Set에 topping의 순서대로 하나씩 넣어가며 나누어진 토핑의 가짓수가 같아지는 지점의 수를 측정하는 것이다.

 

코드 

// O(n) 시간 복잡도 최적화 문제
const solution = (topping) => {
    let answer = 0;
    let bro = new Set();
    let map = new Map();
    
    topping.forEach((e) => {
        map.has(e) ? map.set(e, map.get(e)+1) : map.set(e, 1);
    })
    
    topping.forEach((e) => {
        const cnt = map.get(e) - 1;
        bro.add(e);
        cnt === 0 ? map.delete(e) : map.set(e, cnt);
        
        if(bro.size === map.size) answer += 1;
    })
    
    return answer
}