[프로그래머스 LV2] 롤케이크 자르기

문제

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

첫 번째 풀이

처음에는 이분 탐색으로 생각했다. 공평하게 자를 수 있는 지점을 이분 탐색으로 알아낸 뒤에 그 지점을 기준으로 위 아래로 옮기면서 잘랐을 때에도 공평하다면 결과를 카운팅하는 방식으로 구현했었는데, 시간 초과가 발생했다. 아마도 이분 탐색에서 mid 값을 찾는 과정에 루프가 들어가는데 여기에서 시간 복잡도가 높게 발생하는 것 같다.

소스코드

function slice(topping, start, end) {
  const object = {};
  topping.slice(start, end).forEach(e => (object[e] = true));
  return Object.keys(object);
}

function findMid(topping) {
  let start = 0;
  let end = topping.length;

  while (start < end) {
    const mid = Math.floor((start + end) / 2);
    const left = slice(topping, 0, mid);
    const right = slice(topping, mid, end);

    if (left.length > right.length) end = mid - 1;
    else if (left.length < right.length) start = mid + 1;
    else return mid;
  }
}

function isFairSize(topping, mid) {
  const left = slice(topping, 0, mid);
  const right = slice(topping, mid, topping.length);

  return left.length === right.length;
}

function getResult(topping, mid) {
  let count = 0;

  for (let i = mid; i < topping.length; i++) {
    if (isFairSize(topping, i)) count++;
    else break;
  }

  for (let i = mid - 1; i >= 0; i--) {
    if (isFairSize(topping, i)) count++;
    else break;
  }

  return count;
}

function solution(topping) {
  // 공평하게 자를 수 있는 간략한 위치를 이분 탐색으로 알아낸다.
  const mid = findMid(topping);
  if (typeof mid === 'undefined') return 0;

  // 위 아래로 자르는 위치를 이동해가면서 공평하다면 카운트를 증가한다.
  return getResult(topping, mid);
}

두 번째 풀이

철수가 모든 토핑을 가지고 있고, 이후에 철수가 가지고 있는 토핑을 동생이 하나씩 가져가면서 서로 가지고 있는 토핑의 종류가 일치하면 결과를 카운팅하게끔 구현했다. 그러나 시간 초과가 발생했는데 의심되는 부분은 Object.keys() 로 객체에 들어있는 프로퍼티의 갯수를 체크하는 부분이었다.

소스코드

function solution(topping) {
  var answer = 0;
  const A = {};
  const B = {};

  // 초기에는 모든 토핑을 철수가 가지고 있다고 가정한다.
  topping.forEach(t => {
    if (A[t]) A[t]++;
    else A[t] = 1;
  });

  // 이후에 동생이 토핑을 하나씩 가져간다. 가져갈 때마다 철수의 토핑은 감소시킨다.
  // 만약 (철수가 가진 토핑의 종류 == 동생이 가진 토핑의 종류) 가 되면 결과를 카운팅한다.
  topping.forEach(t => {
    if (B[t]) B[t]++;
    else B[t] = 1;

    if (A[t] > 1) A[t]--;
    else delete A[t];

    const aLength = Object.keys(A).length;
    const bLength = Object.keys(B).length;
    if (aLength === bLength) answer++;
    if (aLength < bLength) return answer;
  });

  return answer;
}

성공한 풀이

두 번째 풀이의 방법과 일치한데, 자료 구조를 Object Literal을 사용하지 않고 Map을 사용했다.

소스코드

function solution(topping) {
  let answer = 0;
  const A = new Map(); // 철수가 갖고 있는 토핑
  const B = new Map(); // 동생이 갖고 있는 토핑

  // 초기에는 모든 토핑을 철수가 가지고 있다고 가정한다.
  topping.forEach(t => {
    if (A.has(t)) A.set(t, A.get(t) + 1);
    else A.set(t, 1);
  });

  // 이후에 동생이 토핑을 하나씩 가져간다. 가져갈 때마다 철수의 토핑은 감소시킨다.
  // 만약 (철수가 가진 토핑의 종류 == 동생이 가진 토핑의 종류) 가 되면 결과를 카운팅한다.
  topping.forEach(t => {
    if (B.has(t)) B.set(t, B.get(t) + 1);
    else B.set(t, 1);

    if (A.get(t) > 1) A.set(t, A.get(t) - 1);
    else A.delete(t);

    if (A.size === B.size) answer++;
    if (A.size < B.size) return answer;
  });

  return answer;
}

느낀 점

평소에 key-value 타입의 자료구조가 필요할 때에는 Object Literal 방식의 객체를 만들어서 사용했었는데, 이번에 Map 자료구조의 효율성을 알게 되었다.
앞으로 키의 추가/삭제가 빈번하게 일어나거나, Iterable 한 기능이 필요하다면 Map을 사용하는 것이 더 낫겠다.