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

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

 

문제복기

이 문제는 시간복잡도를 고려하지 않았을 때는 쉽게 풀 수 있었지만,

시간복잡도까지 고려했을 때는 아이디어가 필요했다.

 

 

시간초과 Ver.

중복을 피해야 하기 때문에 set을 사용했다.

topping의 길이는 최대 1,000,000까지 가능했다.

시간초과 버전에서는 slice를 사용하여 시간초과가 발생했는데, 

slice는 begin부터 end까지 얕은 복사본을 새로운 배열로 반환하는 javascript 메서드다.

 

결국 O(n)의 시간복잡도를 갖는 알고리즘을 만들어야 하는 상황에서

반복문 속의 slice 사용은 O(n * (n/2)) => O(n^2) 의 시간복잡도를 만든다.

function solution(topping) {
    let sum = 0;

    for(let i = 0;i < topping.length;i++) {
      const divider = i;
      const set1 = new Set(topping.slice(0, divider));
      const set2 = new Set(topping.slice(divider));

      if(set1.size === set2.size) {
        sum++;
      }
    }
    
    return sum;
}

 

 

 

문제풀이

이 풀이도 set을 사용해야하는 것은 동일했다.

아래의 풀이 방법은 왼쪽과 오른쪽 각자가 "출발지점"이 된다.

집합의 크기를 좌측 배열, 우측 배열에 각각 넣어준다.

 

롤케이크를 자르는 곳을 i로 하고 왼쪽과 오른쪽을 비교할 것이다.

leftUniqueCount[i]는 왼쪽 끝까지의 집합의 크기를 저장하고 있고,

rightUniqueCount[i+1]는 오른쪽 시작을 의미하고 오른쪽 시작까지의 집합의 크기를 저장하고 있다.

 

우측 배열은 거꾸로 시작을 했기 때문에 집합의 크기는 계속 누적이 되어있었을 것이다.

롤케이크 자르기 - 문제풀이

 

 

둘을 비교하여 같을 때, count를 증가시켜 정답을 구한다.