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

풀이 과정

1. 토핑 종류를 키로, 개수를 값으로 하는 형 객체 생성
   이때 토핑 종류의 수를 따로 세기
2. 토핑 배열에 대해 반복
3. 앞에서부터 해당하는 토핑을 형 객체에서 삭제하고 동생 객체에 추가
   이때 동생 객체의 해당 토핑 수가 0개였으면 동생의 토핑 종류 수 +1
   이때 형 객체의 해당 토핑 수가 0개면 형의 토핑 종류 수 -1
4. 각 과정마다 형과 동생의 토핑 종류 수가 같으면 결과 +1

코드

function solution(topping) {
  let result = 0;
  const older = {};
  let olderCnt = 0;
  const younger = {};
  let youngerCnt = 0;

  topping.forEach((t) => {
    older[t] = (older[t] || 0) + 1;
    if (older[t] === 1) ++olderCnt;
  });

  topping.forEach((t) => {
    younger[t] = (younger[t] || 0) + 1;
    older[t] = older[t] - 1;
    if (younger[t] === 1) ++youngerCnt;
    if (older[t] === 0) --olderCnt;
    if (olderCnt === youngerCnt) ++result;
  });

  return result;
}

🦾

처음에 그냥 Set이랑 slice 했다가 당연히 시간 초과...
사람들 힌트를 참고해서 풀었다.
원소의 개수가 백만 개? => O(n) 풀이를 생각하자