Programmers / Level 2 / 롤케이크 자르기 / JS

문제 간단설명

철수와 동생은 롤케이크를 두조각으로 나눠 먹으려고 한다.

위에 토핑이 올려져 있는데, 둘로 같게 나누는 기준은 토핑 종류의 개수이다.

위에 올라가 있는 토핑 리스트가 주어질 때, 토핑 종류의 개수가 같을 수 있게 나누는 방법이 몇개인지 반환하면 된다.

 

제한 사항

• 1 <= topping의 길이 <= 1,000,000
  • 1 <= topping의 원소 <= 10,000

 

실패 코드 (시간 초과)

function solution(topping) {
    let result = 0;
    
    for(let i=0; i<topping.length; i++) {
        const toppingList1 = topping.slice(0, i + 1);
        const toppingList2 = topping.slice(i + 1, topping.length);
        
        const set1 = new Set(toppingList1);
        const set2 = new Set(toppingList2);
        
        if(set1.size === set2.size) {
            result++;        
        }
    }
    
    return result;
}

 

토핑이 몇개인지 상관없이 '토핑 종류의 개수'만 중요하므로 set 자료구조를 사용했다.

단순히 slice로 케이크를 나누고, 각 set에 집어넣어서 size를 구하면 토핑 종류의 개수가 나온다.

그렇게 양쪽 케이크의 토핑 종류의 개수가 같다면 반환값을 하나 더해주었다.

 

일단 for 반복문은 O(n)의 시간복잡도를 가진다.

그리고 slice또한 O(n)의 시간복잡도를 가진다.

따라서 위 코드는 총 O(n^2)의 시간복잡도를 가진다. 최악의 경우 백만의 제곱이 되기 때문에, 1조가 되므로 시간초과가 날 수 밖에 없다.

 

성공 코드

function solution(topping) {
  // 최대 토핑 종류의 개수
  const COUNT_OF_TOPPING_KIND = 10_000;

  // 토핑 종류별 개수를 저장하는 배열
  const toppingCount1 = Array.from(
    { length: COUNT_OF_TOPPING_KIND + 1 },
    () => 0
  );
  const toppingCount2 = Array.from(
    { length: COUNT_OF_TOPPING_KIND + 1 },
    () => 0
  );

  // 몇 종류의 토핑이 있는지 저장하는 변수
  let count1 = 0;
  let count2 = new Set(topping).size;

  let result = 0;
  // 초기엔 모든 토핑이 2번째 케이크에 올려져 있다고 생각하고 진행한다.
  for (let i = 0; i < topping.length; i++) {
    const kindOfTopping = topping[i];

    toppingCount2[kindOfTopping]++;
  }

  for (let i = 0; i < topping.length; i++) {
    const kindOfTopping = topping[i];

    // 첫번째 케이크에 현재 토핑이 존재하지 않았다면,
    if (toppingCount1[kindOfTopping] === 0) {
      // 토핑 종류의 개수를 하나 늘려준다.
      count1++;
    }
    // 토핑 개수를 증가해준다.
    toppingCount1[kindOfTopping]++;

    // 두번째 케이크에서 현재 토핑을 빼준다.
    toppingCount2[kindOfTopping]--;
    // 두번째 케이크에 현재 토핑이 존재하지 않는다면,
    if (toppingCount2[kindOfTopping] === 0) {
      // 토핑 종류의 개수를 하나 빼준다.
      count2--;
    }

    // 양쪽 케이크의 토핑 종류의 개수가 같다면,
    if (count1 === count2) {
      // 결과값을 하나 늘려준다.
      result++;
    }
  }

  return result;
}

 

토핑 종류의 개수가 10,000개이므로 각 케이크마다 각 토핑 종류의 개수를 저장하는 배열을 만들어주었다.

그리고 자르기전엔 한 케이크가 모든 토핑을 가지고 있으므로, 그것을 두번째 케이크에 있다고 가정하고 해주었다.

 

토핑리스트를 순회하면서, 첫번째 케이크에 없던 토핑이라면 카운트를 하나 더해주었다.

그리고 첫번째 케이크의 토핑 종류의 개수를 하나 늘려주었다.

 

두번째 케이크에 있던 토핑을 첫번째 케이크가 가져갔으므로, 두번째 케이크에서 해당 토핑의 개수를 하나 빼준다. 그리고 해당 토핑의 개수가 0이 되었다면, 토핑 종류의 개수를 하나 빼주었다.

 

위 과정을 거친 뒤 양쪽 케이크의 토핑 종류의 개수가 같다면 반환값을 하나 늘려주었다.

 

위 코드는 실패코드와 달리 slice 같은 반복 메서드도 없고, for문 하나만 존재하므로 O(n)의 시간복잡도를 가진다.