프로그래머스 롤케이크 자르기 - 자바스크립트

📄 문제

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

구현해야 하는 것은

롤케이크를 두 조각으로 나뉘게 잘랐을 때, 각 조각에 올려진 토핑 종류의 개수가 같아야 한다.

예를 들어 아래 그림과 같이 롤케이크에 토핑이 올려져 있다고 가정해보자.

이미지 출처 : https://www.ssg.com/item/itemView.ssg?itemId=1000518951902&siteNo=6001&salestrNo=6005&ckwhere=ssg_daum&appPopYn=n&utm_medium=PCS&utm_source=daum&utm_campaign=daum_pcs

왼쪽에서부터 순서대로 토핑을 배열에 담으면 [🍓, 🥝, 🍑, 🍓, 🍓, 🥝, 🍑, 🍒]다. 그리고 4번째와 5번째 사이를 자른다.

그럼 롤케이크는 [🍓, 🥝, 🍑, 🍓]가 있는 조각과 [🍓, 🥝, 🍑, 🍒]가 있는 조각으로 나뉘게 된다. 왼쪽 조각의 토핑 갯수는 4개다. 하지만 토핑 종류는 3개다(🍓가 두 번 들어있음). 오른쪽 조각도 토핑 갯수는 4개이지만 토핑 종류는 모두 다르므로 4개다. 결국 왼쪽 조각은 3개의 토핑을 맛볼 수 있고, 오른쪽 조각은 4개의 토핑을 맛볼 수 있으므로 공평하게 나눈 것이 아니다.

이미지 출처 : https://www.ssg.com/item/itemView.ssg?itemId=1000518951902&siteNo=6001&salestrNo=6005&ckwhere=ssg_daum&appPopYn=n&utm_medium=PCS&utm_source=daum&utm_campaign=daum_pcs

이번엔 토핑이 [🍓, 🥝, 🍓, 🍓, 🥝, 🍓, 🍓, 🍓]로 들어있고, 두 번째와 세 번째 사이를 자른다. 먹을 수 있는 토핑의 총 갯수는 왼쪽 조각에 2개, 오른쪽 조각에 6개이지만 토핑 종류는 🍓, 🥝로 양쪽 다 2개다. 이 경우는 공평하게 나눈 것이다.

결국 몇 개의 토핑을 먹느냐보다 몇 가지의 토핑을 먹느냐가 중요한 것이다. 총량은 중요하지 않고 가짓수를 구해야 하므로 조각을 나눠서 토핑의 중복을 없앤 후 양쪽의 갯수가 일치하는지 확인해야 한다.

😫 실패한 사례를 먼저 보자.

특정 토핑이 어느 조각에 올라가 있는지에 대해 모든 경우를 고려해야 하므로 topping 배열을 순회하는 작업이 필요하다.

전체 토핑 값이 담겨있는 배열(A)의 요소를 하나씩 제거해서 다른 배열(B)로 삽입하고, A와 B의 중복을 없앤 요소의 갯수를 비교해서 일치하면 방법의 수를 누적시키려고 했다.

A의 마지막 요소를 제거(pop())하여 B에 삽입(push())하기로 했다. 그 후 Set으로 중복을 제거하고 각각 Set의 길이를 비교했다. 코드는 다음과 같다.

const solution = (topping) => {
  const temp = [];
  let result = 0;
  let tempCnt, toppingCnt;

  while (topping.length > 0) {
    temp.push(topping.pop());

    tempCnt = new Set(temp).size;
    toppingCnt = new Set(topping).size;

    if (tempCnt === toppingCnt) result++;
  }

  return result;
};

시간 초과가 발생했다. 시간 복잡도를 계산해보면 while문으로 전체 배열을 순회하기 위해 O(n), 부분 배열을 Set으로 변경하기 위해 또 순회하므로 O(n)으로 총 O(n²)이 된다.

제한사항이 1 ≤ topping의 길이 ≤ 1,000,000이므로 길이가 긴 배열이 들어왔을 때는 시간 초과가 발생한다. 그러므로 중첩 반복을 피해서 부분 배열의 요소 갯수를 구하는 방법을 생각해야 한다.

그래서 반복을 두 번하긴 하되, 중첩없이 각각 순회하면서 원하는 값을 얻어내기로 했다.

1️⃣ 먼저 전체 배열을 순회하면서 토핑 종류의 갯수를 파악했다.

Map 객체의 키 값은 고유하다. 즉, 키 값은 중복되지 않는다. 토핑 현황을 관리하기 위해서 토핑을 key로, 토핑 갯수를 value로 하는 요소를 갖는 Map을 선언한다.

위에서 언급한 [🍓, 🥝, 🍑, 🍓, 🍓, 🥝, 🍑, 🍒]의 토핑 종류를 Map에 저장하면 {🍓 => 3, 🥝 => 2, 🍑 => 2, 🍒 => 1} 가 된다.

const solution = (topping) => {
  const map1 = new Map();

  topping.forEach((t) => {
    map1.set(t, (map1.get(t) || 0) + 1);
  });
};

이제 map1에는 롤케이크의 토핑의 종류와 갯수가 들어있다.

2️⃣ 롤케이크를 자르며 생긴 나머지 조각의 토핑 종류의 갯수를 저장하고, 원래 조각에서의 해당 토핑의 갯수를 갱신해야 한다.

롤케이크 전체에서 토핑을 하나씩 제거할 것이므로 특정 토핑이 제거될 때 1️⃣에서 만든 Map에서 해당 토핑의 갯수를 제거하고, 제거한 토핑이 담긴 새로운 조각의 토핑 현항을 관리하는 새로운 Map에 추가한다.

원래 전체 조각을 A, 새로 자른 조각을 B라고 하자.

전체 조각 A는 [🍓, 🥝, 🍑, 🍓, 🍓, 🥝, 🍑, 🍒]이다. A조각의 토핑 종류와 갯수 현황을 Map에 담으면 {🍓 => 3, 🥝 => 2, 🍑 => 2, 🍒 => 1}이다. 여기서 가장 마지막 토핑 앞에서 자른다면 전체 조각에서 🍒가 없어지는 것이다. 그러므로 토핑 갯수는 {🍓 => 3, 🥝 => 2, 🍑 => 2, 🍒 => 0}이 된다.

그리고 칼로 자르면서 새로 생긴 조각 B는 [🍒]이다. B의 토핑 현황은 {🍒 => 1}이다.

A에 있던 토핑이 B로 이동한 것이므로 A의 토핑을 관리하는 Map에서는 🍒의 토핑 갯수를 1 감소시키고, B의 토핑을 관리하는 Map에는 🍒의 토핑 갯수를 1 증가시킨 것이다. 그리고 A는 🍒가 하나도 없기 때문에 A 조각의 토핑을 관리하는 Map에서 🍒를 key로 갖는 요소를 delete를 해준다.

그러면 A는 3개의 토핑(🍓, 🥝, 🍑), B는 1개의 토핑(🍒)을 맛볼 수 있으므로 공평하지 않다. 이 작업을 A에 있는 토핑이 B로 모두 넘어올 때까지 수행해야 한다.

[🍓, 🥝, 🍑, 🍓, 🍓], [🥝, 🍑, 🍒]으로 자른다면 토핑 현황은 A는 {🍓 => 3, 🥝 => 1, 🍑 => 1}, B는 {🥝 => 1, 🍑 => 1, 🍒 => 1}이 된다. 양쪽 모두 3개의 토핑을 맛볼 수 있으므로 공평한 것이다.

const solution = (topping) => {
  const map2 = new Map();

  // ...

  topping.forEach((t) => {
    //map1에 있는 토핑을 하나씩 가져온다. 그러므로 map2는 1씩 증가하고, map1은 1씩 감소한다.
    map2.set(t, map2.get((t || 0) + 1));
    map1.set(t, map1.get(t) - 1);

    // value가 0인 것은 해당 조각에 토핑이 하나도 존재하지 않는 것이므로 제거한다.
    if (map1.get(t) === 0) map1.delete(t);

    // size가 같은 것은 중복을 제거한 토핑 종류의 갯수가 일치하는 것이므로 공평한 방법의 수를 1 증가시킨다.
    if (map1.size === map2.size) result++;
  });
};

🏹 코드

const solution = (topping) => {
  let result = 0;
  const map1 = new Map();
  const map2 = new Map();

  topping.forEach((t) => {
    map1.set(t, (map1.get(t) || 0) + 1);
  });

  topping.forEach((t) => {
    map2.set(t, map2.get((t || 0) + 1));
    map1.set(t, map1.get(t) - 1);

    if (map1.get(t) === 0) map1.delete(t);

    if (map1.size === map2.size) result++;
  });

  return result;
};

👩‍🌾 새로 알게 되었거나 중요한 포인트

최대한 쉽게 설명하려다 보니 글이 굉장히 길어졌지만 배열의 순회하며 값을 얻어야 할 때 어떻게 하면 시간 복잡도를 줄일 수 있을까를 고민해봐야 하는 문제다. ~(이모지를 이용하면 쉽게 풀어낼줄 알았는데 너무 많이 써버려서 가독성이 떨어진다…)~

이전에 배열의 중복을 제거하기 위한 방법으로 Set을 사용했던 것을 떠올려 이번에도 Set을 사용하려고 했지만 시간 초과가 발생했다.

실패한 사례와 통과한 사례의 코드를 살펴보면 둘 다 2번의 반복을 통해 토핑을 한쪽에서 다른쪽으로 하나씩 옮겨가며 결과를 얻어내지만 실패 사례는 중첩 반복으로 O(n) * O(n) = O(n²)이 되고, 성공 사례는 반복을 연달아서 두 번하며 O(n) + O(n) = O(n)이 된다.

제한 사항에 배열의 길이가 큰 경우에는 중첩이나 시간 복잡도가 큰 메서드의 사용을 지양해서 시간 복잡도를 줄여서 해결하도록 하자.