Boongranii

최고의 열정을 뽐내는 쿼카 🐶

3 분 소요

예순 다섯 번째 포스팅

안녕하세요! 예순 다섯 번째 포스팅으로 찾아뵙게 되어 반갑습니다!♥

오늘의 포스팅 내용은 프로그래머스 - 롤케이크 자르기에 관한 내용입니다.
자세한 내용을 알아보러 갑시다❗️

[Boongranii] Here We Go 🔥

1️⃣ 문제

[프로그래머스] 롤케이크 자르기 (문제 링크)

💨 문제 설명

철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다.

예를 들어, 롤케이크에 4가지 종류의 토핑이 올려져 있다고 합시다. 토핑들을 1, 2, 3, 4와 같이 번호로 표시했을 때, 케이크 위에 토핑들이 [1, 2, 1, 3, 1, 4, 1, 2] 순서로 올려져 있습니다. 만약 세 번째 토핑(1)과 네 번째 토핑(3) 사이를 자르면 롤케이크의 토핑은 [1, 2, 1], [3, 1, 4, 1, 2]로 나뉘게 됩니다. 철수가 [1, 2, 1]이 놓인 조각을, 동생이 [3, 1, 4, 1, 2]가 놓인 조각을 먹게 되면 철수는 두 가지 토핑(1, 2)을 맛볼 수 있지만, 동생은 네 가지 토핑(1, 2, 3, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것이 아닙니다. 만약 롤케이크의 네 번째 토핑(3)과 다섯 번째 토핑(1) 사이를 자르면 [1, 2, 1, 3], [1, 4, 1, 2]로 나뉘게 됩니다. 이 경우 철수는 세 가지 토핑(1, 2, 3)을, 동생도 세 가지 토핑(1, 2, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것입니다. 공평하게 롤케이크를 자르는 방법은 여러가지 일 수 있습니다. 위의 롤케이크를 [1, 2, 1, 3, 1], [4, 1, 2]으로 잘라도 공평하게 나뉩니다. 어떤 경우에는 롤케이크를 공평하게 나누지 못할 수도 있습니다.

롤케이크에 올려진 토핑들의 번호를 저장한 정수 배열 topping이 매개변수로 주어질 때, 롤케이크를 공평하게 자르는 방법의 수를 return 하도록 solution 함수를 완성해주세요.

💨 제한 사항

  • 1 ≤ topping의 길이 ≤ 1,000,000
    • 1 ≤ topping의 원소 ≤ 10,000

💨 입출력 예

topping result
[1, 2, 1, 3, 1, 4, 1, 2] 2
[1, 2, 3, 1, 4] 0

💨 입출력 예 설명

입출력 예 #1

롤케이크를 [1, 2, 1, 3], [1, 4, 1, 2] 또는 [1, 2, 1, 3, 1], [4, 1, 2]와 같이 자르면 철수와 동생은 각각 세 가지 토핑을 맛볼 수 있습니다. 이 경우 공평하게 롤케이크를 나누는 방법은 위의 두 가지만 존재합니다.

입출력 예 #2

롤케이크를 공평하게 나눌 수 없습니다.

2️⃣ 문제 풀이

🔥 시간 초과 해결 풀이

  1. 시간 복잡도를 줄이기 위한 방법임.
  2. 좌측과 우측의 토핑 수를 넣을 배열을 생성
  3. 좌측과 우측의 토핑 수를 비교하여 같다면 count++
  4. count를 반환
  5. 시간 복잡도는 O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

function solution(topping) {
  let count = 0;

  const leftCount = Array.from({ length: topping.length }).fill(0);
  const rightCount = Array.from({ length: topping.length }).fill(0);

  const leftSet = new Set();
  const rightSet = new Set();

  for (let i = 0; i < topping.length; i++) {
    leftSet.add(topping[i]);
    leftCount[i] = leftSet.size;
  }

  for (let i = topping.length - 1; i >= 0; i--) {
    rightSet.add(topping[i]);
    rightCount[i] = rightSet.size;
  }

  for (let i = 0; i < topping.length - 1; i++) {
    if (leftCount[i] === rightCount[i + 1]) {
      count++;
    }
  }

  return count;
}

console.log(solution([1, 2, 1, 3, 1, 4, 1, 2])); // 2

주어진 문제를 해결하기 위한 아이디어는 꽤나 간단하다. 하지만, 제한사항을 보면 알다시피 굉장히 순회를 많이 하게 된다. 따라서 시간복잡도를 줄이는 풀이를 작성하여 해결해야 한다.

배열을 두 번 순회하여 왼쪽과 오른쪽의 서로 다른 토핑의 종류의 수를 계산하고 비교해야 한다.

배열의 왼쪽부터 순회하며 각 위치까지의 서로 다른 토핑의 수를 계산하여 leftCount에 저장한다.

또한, 배열의 오른쪽부터 순회하며 각 위치까지의 서로 다른 토핑 수를 계산하여 rightCount에 저장한다.

이제 왼쪽과 오른쪽의 개수를 비교해 가면서 일치한다면 경우의 수를 증가시키면 된다.

막상 이렇게 보면 되게 간단한 듯하지만 예전에 해결하려 했다가 이번에 풀어보았다.

🔥 시간 초과 풀이

  1. slice()를 통해 겹치지 않게 잘라가며 순회함.
  2. Set을 통해 각 배열의 중복된 부분을 제거한다.
  3. 각 배열의 길이가 같다면 공정하게 자른 것임.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function solution(topping) {
  let result = 0;
  const array = [];

  for (let i = 1; i < topping.length - 1; i++) {
    const arr1 = topping.slice(0, i);
    const arr2 = topping.slice(i);
    array.push([[...new Set(arr1)], [...new Set(arr2)]]);
  }

  array.forEach((a) => {
    if (a[0].length === a[1].length) {
      result++;
    }
  });

  return result;
}

처음에 위와 같은 풀이로 접근하였다. 하지만 slice()를 사용한 순회는 엄청난 시간 복잡도를 가져오며 시간 초과를 야기한다. 또한 반복문 안에 있는 Set을 계속해서 사용하는 과정이 반복되기 때문에 굉장히 비효율적이다.

위와 같은 문제로 인해 시간 복잡도가 급격하게 증가하여 큰 입력값에 대해서는 시간 초과가 발생하게 되는 것이다!

3️⃣ 느낀점

유연한 사고를 기르는 것이 중요할 것 같다. 제한사항도 값이 엄청나게 크면 O(n) 급으로 맞추어 풀도록 노력해야겠다.

시간 초과 풀이는 다시 봐도 너무 억지 풀이긴 하다. 억풀억풀. 화이팅팅털❗️💕

댓글남기기

참고