프로그래머스 Lv.2(JS) - 롤케이크 자르기

문제

정답

풀이 코드

function solution(topping) {
  let oldBro = new Set(topping).size;
  const youngBro = new Set();
  let restToppings = topping.slice();
  let result = 0;

  const lastToppings = new Map();
  new Set(topping).forEach((x) => lastToppings.set(x, topping.indexOf(x)));

  for (let i = topping.length - 1; i >= 0; i--) {
    let cutTopping = restToppings.pop();
    youngBro.add(cutTopping);

    if (i === lastToppings.get(topping[i])) oldBro--;
    if (oldBro === youngBro.size) result++;
  }

  return result;
}

풀이 설명

function solution(topping) {
  let oldBro = new Set(topping).size;
  const youngBro = new Set();
  let restToppings = topping.slice();
  let result = 0;

  const lastToppings = new Map();
  new Set(topping).forEach((x) => lastToppings.set(x, topping.indexOf(x)));
  //...
}

• oldBro와 youngBro는 각각 철수와 동생이 롤케이크를 자르면서 가지는 토핑의 수를 나타내며, 중복을 제외한 토핑 수를 세기 위해 oldBro(철수)와 youngBro(동생)를 Set으로 생성합니다. oldBro가 전체 롤케이크를 가지고 있고 동생에게 나눠준다고 가정하여 oldBro는 전체 토핑 배열의 중복을 제거한 개수로 초기화합니다.

• restToppings는 롤케이크를 뒤에서부터 자르면서 남는 토핑 배열입니다. topping은 반복문으로 순회할 것이므로 원본 배열의 요소 변경을 방지하기 위해 복사하여 할당합니다.

• lastToppings를 Map으로 생성하고 (key가 number 타입) 토핑별 첫 번째 인덱스값(뒤에서부터 잘랐을 때, 마지막으로 남은 토핑 위치)을 저장합니다.

function solution(topping) {
  //...
  for (let i = topping.length - 1; i >= 0; i--) {
    let cutTopping = restToppings.pop();
    youngBro.add(cutTopping);

    if (i === lastToppings.get(topping[i])) oldBro--;

    if (oldBro === youngBro.size) result++;
  }

  return result;
}

• topping을 거꾸로 순회하면서 토핑을 youngBro에게 전달합니다. Set으로 생성되어 있으므로 중복 값은 제외되고 고유 토핑만 남습니다.

• 잘라 주려는 토핑이 철수가 가진 토핑의 마지막 위치인 경우 철수가 가진 토핑에서도 -1씩 제거합니다.

• 철수와 동생이 가진 고유 토핑 수가 동일하다면 result를 증가시킵니다.

References

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