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

문제 출처

프로그래머스 lev2 - 롤케이크 자르기

나의 풀이

1차시도 (25/100)

function solution(topping) {
  let answer=0;
  let lt=0; 
  let rt=topping.length-1;

  while(lt<=rt) {
    let mid=parseInt((lt+rt)/2);
    let left = new Set(topping.slice(0,mid))
    let right = new Set(topping.slice(mid))
    console.log(mid, left, right);
    if(left.size == right.size) {
      answer++;
      rt=mid-1;
    }

    else if(left.size > right.size) rt=mid-1;
    else if(left.size < right.size) lt=mid+1;
  }
  return answer;
}

console.log(solution([1, 2, 1, 3, 1, 4, 1, 2]));
// console.log(solution([1, 2, 3, 1, 4]));

다른 풀이

해시맵을 통해 미리 토핑 정보를 저장한다.

그리고 매번 left와 right의 토핑 개수를 계산하면 시간초과가 발생하므로,
토핑 개수를 미리 right에 몰아넣고 토핑 개수를 빼거나 넣으며 비교한다.
left=0, right=info.size

topping을 순회하면서 개수가 남아 있으면 감소시켜주다가 개수가 0개가 될 때 right의 토핑 개수를 감소시켜준다.
그리고 처음 만나는 토핑이면 left를 증가시켜준다.

둘이 같아지는 지점에서 res++ 해준다.

const solution = (topping) => {
  const info = new Map();
  topping.forEach(el => {
      if (info.has(el)) {
          const val = info.get(el);
          val.amount++;
          info.set(el, val);
      } else {
          info.set(el, { amount: 1, visited: false });
      }
  });
  // console.log(info);

  let res = 0;
  let [left, right] = [0, info.size];
  for (let i = 0; i < topping.length; i++) {
    // console.log(left, right);
    const val = info.get(topping[i]);
    if (val.amount >= 1) {
        val.amount--;
        if (val.amount === 0) right--;
    }
    if (!val.visited) { val.visited = true; left++; }
    info.set(topping[i], val);
    if (left === right) res++;
  }

  return res;
}

function solution(topping) {
  const a = new Set()
  const b = {}

  let answer = 0;
  let check = 0

  for (let i = 0; i < topping.length; i++) {        
    if (b[topping[i]]) {
        b[topping[i]]++
    } else {
        b[topping[i]] = 1
        check++            
    }
  }

  for (let i = 0; i < topping.length; i++) {
    a.add(topping[i])
    b[topping[i]]--
    if (!b[topping[i]]) check--
    if (a.size === check) answer++
  }
  return answer;
}