프로그래머스 JS 토핑 나누기

문제 요약

케이크가 있고 형동생은 케이크를 공평하게 나눠먹어야 한다. 공평하다는 조건은 위에 토핑의 종류가 같아야 한다는 것
토핑의 갯수는 상관없고 토핑의 종류가 같아야 한다.

내가 시도한 방법

공평하게 나눠야 하니 처음에 반을 갈러서 형 동생의 토핑을 정해주고
전체 토핑에서 왼쪽 오른쪽으로 이동하면서 형의 토핑을 동생으로 옮겨주고
동생의 토핑을 형으로 옮겨줘서 같을때를 체크 하도록 설계했다.

첫번째 시도

function solution(topping) {
  var answer = 0;
  let sameArr = [];
  let half = Math.floor(topping.length / 2) - 1;
  let toppingCount = Math.max(...topping);

  let aCake = Array.from({ length: toppingCount + 1 }, () => 0);

  let bCake = aCake.slice(0);
  for (let index in topping) {
    let t = topping[index];
    let target = index < half + 1 ? aCake : bCake;
    // console.log(t, index, target);
    target[t]++;
  }
  console.log(aCake, bCake);
  let now = half + 1;
  // 두방향으로 반복문 만드는게 나을듯
  let cNow = now;
  let cACake = aCake.slice(0);
  let cBCake = bCake.slice(0);
  while (true) {
    // 오른쪽으로 이동
    if (cNow >= topping.length || toppingSize(cACake) > toppingSize(cBCake)) {
      break;
    }

    let t = topping[cNow];
    cBCake[t]--;
    cACake[t]++;
    // console.log(cNow, t, toppingSize(cACake), toppingSize(cBCake));
    if (toppingSize(cACake) === toppingSize(cBCake)) {
      sameArr.push(cNow);
    }
    cNow++;
  }

  cNow = now;
  cACake = aCake.slice(0);
  cBCake = bCake.slice(0);
  while (true) {
    // 왼쪽으로 이동

    if (cNow <= 0 || toppingSize(cACake) < toppingSize(cBCake)) {
      break;
    }

    let t = topping[cNow];
    console.log(cNow, t, cACake, cBCake);
    cBCake[t]++;
    cACake[t]--;
    if (toppingSize(cACake) === toppingSize(cBCake)) {
      sameArr.push(cNow);
    }
    cNow--;
  }
  console.log(sameArr);
  return;

  return answer;
}
function toppingSize(arr) {
  arr = arr.filter((x) => x > 0);
  return arr.length;
}
solution([1, 2, 1, 3, 1, 4, 1, 2]);
//2

결과 런타임 에러가 나온다.

이유가 뭘까 생각해보니
나는 간단하게 배열로 풀려고 해서 배열 인덱스로 토핑을 생각했는데
토핑이 [1,.2,3,4,100] 이렇게 주어진다면
now 가 7이라면 undefined가 나와서 런타임 에러가 나오는것 같다.

문제에서도 확실히 토핑이 숫자 순서대로 나온다는 말이 언급 되지 않았다.

객체 형태로 바꿔서 다시 트라이

두번째 시도

function solution(topping) {
  var answer = 0;
  let sameArr = [];
  let half = Math.floor(topping.length / 2) - 1;

  let aCake = new Map();

  let bCake = new Map();

  for (let index in topping) {
    let t = topping[index];
    let target = index < half + 1 ? aCake : bCake;
    let nonTarget = target === aCake ? bCake : aCake;
    // console.log(t, index, target);

    target.set(t, target.has(t) ? target.get(t) + 1 : 1);
    nonTarget.set(t, nonTarget.has(t) ? nonTarget.get(t) : 0);
  }

  let now = half + 1;

  let cNow = now;
  let cACake = new Map(aCake);
  let cBCake = new Map(bCake);
 
  while (true) {
    // 오른쪽으로 이동
    if (cNow >= topping.length || toppingSize(cACake) > toppingSize(cBCake)) {
      break;
    }

    let t = topping[cNow];
    cBCake.set(t, cBCake.get(t) - 1);
    cACake.set(t, cACake.get(t) + 1);

    console.log(
      cNow,
      t,
      toppingSize(cACake),
      toppingSize(cBCake),
      cBCake,
      cACake
    );
    if (toppingSize(cACake) === toppingSize(cBCake)) {
      sameArr.push(cNow);
    }
    cNow++;
  }

  cNow = now;
  cACake = new Map(aCake);
  cBCake = new Map(bCake);

  while (true) {
    // 왼쪽으로 이동

    if (cNow <= 0 || toppingSize(cACake) < toppingSize(cBCake)) {
      break;
    }

    let t = topping[cNow];
    console.log(cNow, t, cACake, cBCake);
    cBCake.set(t, cBCake.get(t) + 1);
    cACake.set(t, cACake.get(t) - 1);
    if (toppingSize(cACake) === toppingSize(cBCake)) {
      sameArr.push(cNow);
    }
    cNow--;
  }
  console.log(sameArr, "답");
  return;

  return answer;
}
function toppingSize(map) {
  let count = 0;
  for (let v of map.values()) {
    if (v > 0) count++;
  }
  return count;
}
solution([1, 1, 4, 7, 7, 5]);
//2

시간초과가 나온다
아무래도 for문이 3개로 너무 많은것 같다 특히나
toppingSize는 매번 2번씩 map 을 돌아야 해서 쓸데없이 낭비되는것 같았다
아예 새로운 방법으로 트라이 해야 겠다고 생각하게 되었다.

3번째 도전 어떻게 접근하면 좋을까 하다가
처음에 형이 먼저 토핑을 가지고 있다가 동생이 하나씩 빼먹으면서 같게 되는 부분만 체크 해보자 라고 생각 하고 코드를 짜게 되었다.

3번째 트라이

var answer = 0;
 let sameArr = [];
 let half = Math.floor(topping.length / 2) - 1;

 let aCake = new Map();

 let bCake = new Set();

 for (let index in topping) {
   let t = topping[index];

   aCake.set(t, aCake.has(t) ? aCake.get(t) + 1 : 1);
 }
 let i = 0;
 while (true) {
   if (bCake.size > aCake.size) {
     break;
   }
   if (bCake.size === aCake.size) {
     sameArr.push(i);
   }
   let t = topping[i];
   aCake.set(t, aCake.get(t) - 1);
   if (aCake.get(t) === 0) {
     aCake.delete(t);
   }
   bCake.add(t);

   i++;
 }

통과 할수 있었다.
다만 시간은 만족스럽지는 못했다
그래도 코드는 while문 한개로 반복문을 많이 줄이고 코드량도 많이 줄일수 있었다.
이 방법을 왜 바로 생각하지 못했을까
공평하게 라고 써있고 케이크를 생각하자마자 반을 먼저 갈라 시작을 하는게 떠올라서
반을 나눠서 왼쪽 오른쪽 나눠서 반복문을 구하다보니 코드가 복잡해진것 같다.
문제를 먼저 어떻게 접근해야 할지 설계해야 할지가 매우 중요한것 같다.