[알고리즘] 프로그래머스 - 롤케이크 자르기

문제 설명 

 

제한 사항

• 1 <= topping의 길이 <= 1,000,000
  • 1 <= topping의 원소 <= 10,000

입출력 예

topping	result
[1, 2, 1, 3, 1, 4, 1, 2]	2
[1, 2, 3, 1, 4]	0

 

내 코드

sol 1.

**** 시간 초과 오답 ****

function solution(topping) {
  let answer = 0;
  const oldToppingSet = new Set(); // 철수 토핑
  const youngToppingSet = new Set(); // 동생 토핑
  let cutIdx = 1;

  while (cutIdx > -1 && cutIdx < topping.length) {
    for (let i = 0; i < cutIdx; i++) {
      oldToppingSet.add(topping[i]);
    }
    for (let j = cutIdx; j < topping.length; j++) {
      youngToppingSet.add(topping[j]);
    }

    if (oldToppingSet.size > youngToppingSet.size) break;
    if (oldToppingSet.size === youngToppingSet.size) answer++;

    cutIdx++;
    oldToppingSet.clear();
    youngToppingSet.clear();
  }
  return answer;
}

• while 루프에서 시간 복잡도 최대 N
• 두개의 for문 각각 최대 N
• 최악의 경우 시간 복잡도 O(N^2)
  
  • 토핑의 길이가 최대 1,000,000이므로 정답을 돌렸을 때 오답이 뜸

 

sol 2

function solution(topping) {
  let answer = 0;
  const map = new Map(); //전체 토핑 개수로, for문이 돌면 동생의 토핑수가 된다.
  const broTopping = new Set();

  for (let i = 0; i < topping.length; i++) {
    map.has(topping[i])
      ? map.set(topping[i], map.get(topping[i]) + 1)
      : map.set(topping[i], 1);
  }

  for (let i = 0; i < topping.length; i++) {
    // 토핑을 하나씩 형한테 줌
    let cnt = map.get(topping[i]) - 1;
    broTopping.add(topping[i]);

    cnt == 0 ? map.delete(topping[i]) : map.set(topping[i], cnt);

    if (broTopping.size === map.size) answer++;
  }
  return answer;
}

• Map의 성질을 활용해 효과적인 비교를 수행함
• 토핑의 개수를 저장하여 두번째 for문을 순회할 때 broTopping을 업데이트하도록 함
• 단독으로 N번씩 실행 -> 시간 복잡도 : O(n)